Den produkt homomorfism problem (PHP) tar som ingång en ändlig samling av relationella strukturer A 1,. ., A n och en annan relationsstruktur B, över samma schema, och frågar om det finns en homomorfism från den direkta produkten A 1 × · · · × A n till B. Detta problem kan helt klart lösas i icke-deterministisk exponentiell tid. Det framgår av resultaten i [1] att problemet är NExpTimefullständig. Beviset, som bygger på en minskning från ett exponentiellt tiling problem, använder strukturer av avgränsade domänstorlek men med relationer av obegränsad aritualitet. I denna not ger vi ett fristående bevis på NExpTime-hårdhet i PHP, och vi visar att det redan innehar för riktade grafer, liksom för strukturer av avgränsad aritualitet med en avgränsad domänstorlek (men utan en gräns på antalet relationer). Mer exakt får vi:. Den nedre gränsen håller redan för 1. strukturer med binära relationer och en avgränsad domänstorlek; 2. strukturer med en enda relation och en avgränsad domänstorlek; Detta kompletterar bilden, eftersom PHP kan lösas i polynom tid när alla tre av ovanstående parametrar (dvs. antal relationer, arity, och domänstorlek) begränsas, som följer av det faktum att det i detta fall endast finns ändligt många olika möjliga inmatning strukturer upp till isomorfism. Teorem 1.1 bevisas genom en anpassning av den teknik som används i [1]. Teorem 1.2 bevisas genom en minskning från 1.1. Teorem 1.3 bevisas genom en minskning från Theorem 1.2. Vi presenterar också en tillämpning av ovanstående resultat på CQ-definibilitet problem (även känd som PP-definiability problem). Bevis. Genom att minska från det exponentiella tiling problemet. Vi antar en fast uppsättning av kakel typer med tillhörande horisontella och vertikala kompatibilitetsrelationer, och inmatningen av tiling problemet består av ett heltal m (specificeras i unary) tillsammans med en sekvens av (inte nödvändigtvis distinkt) kakel typer t 1,. .., t m. Problemet är att avgöra om 2 m -by-2 m rutnätet har en giltig tiling där t 1,. .., t m är ett prefix av sekvensen av plattor på den första raden, med början vid ursprung. Det är känt att det finns en fast ändlig uppsättning av kakel typer som detta problem är NExpTime-hård. För att underlätta utläggningen kommer vi också att använda oss av unary relations. Dessa kan enkelt ersättas av binära. Tanken med minskningen är mycket enkel. Vi kommer att definiera 2m strukturer, A 1,. ., A 2m, var och en har domän {0, 1}. På detta sätt, varje del av produkten Π i A i är en bitsträng av längd 2m, som vi kommer att tolka som ett par bisträngar av längd m, där den första bitsträngen är den binära kodningen av en * Vi är tacksamma till Ross Willard för diskussioner om ämnet och för kommentarer om ett tidigare utkast.
Se även noten av Ten Cate och Dalmau REF för en relation med produkten homomorfism problem som innebär att CQ-definibilitet är redan conexptime-hård för unary frågor över en fast schema som består av en enda binär relation.
A note on the product homomorphism problem and CQ-definability
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}