Låt A vara en idempotent algebra på en ändlig domän. Vi kombinerar resultat från Chen [11], Zhuk [24] och Carvalho et al. [7] att hävda att om A uppfyller den polynomiskt genererade makten egendom (PGP), då QCSP(Inv(A)) är i NP. Vi använder sedan resultatet av Zhuk för att bevisa en omvänt, att om Inv(A) uppfyller exponentiellt genererade befogenheter egendom (EGP), då QCSP(Inv(A)) är co-NP-hård. Eftersom Zhuk bevisade att endast PGP och EGP är möjliga, får vi en fullständig dikotomi för QCSP, som rättfärdigar den moraliska korrektheten av vad vi kallar Chen Conjecture (se [12]). Vi undersöker närmare situationen för områden av storlek tre. Över alla ändliga domäner är den enda typen av PGP som kan uppstå utbytbarhet. Chen införde utbytbarhet [11] som en generalisering av den redan kända Collapsibility [9]. För tre element domän algebras A som är utbytbara, visar vi att för varje ändlig delmängd av Inv(A), Pol( på) är Collapsible. Betydelsen av detta är att, för QCSP på finita strukturer (över tre element domän), alla QCSP dragbarhet förklaras av Switchability redan förklaras av Collapsibility. Slutligen presenterar vi en tre-element domän komplexitet klassificering vinjett, med hjälp av kända såväl som härledda resultat.  ACM Subject Classification F.2.2 Nonnumerical Algorithms and Problems Keywords and Frases En stor mängd arbete finns från de senaste tjugo åren på tillämpningar av universell algebra till den beräkningsmässiga komplexiteten av begränsningar tillfredsställelse problem (CSPs) och ett antal hyllade resultat har erhållits genom denna metod. Man tar hänsyn till problemet CSP(B) där det frågas om det finns en indatamening på B, där det är primitivt positivt, det vill säga att använda endast  på, och =. CSP är ett av en bred klass av modellkontrollproblem som erhålls från begränsningar av första ordningens logik. För nästan var och en av dessa klasser kan vi ge en komplexitetsklassificering [18]: de två återstående klasserna är CSP och dess populära förlängning kvantifierade CSP (QCSPs) för positiva Horn meningar - där det också finns - som används i Artificiell Intelligens för att modellera icke-monoton resonemang eller osäkerhet [15]. Den enastående hypotesen i området är att alla ändliga-domän CSPs är antingen i P eller NP-komplett, något överraskande med tanke på dessa CSPs verkar bilda en stor mikrokosmos av NP, och NP i sig är osannolikt att ha denna dikotomi egendom. Denna Feder-Vardi gissning [16], som ges mer konkret i algebraiska språket i [6], förblir orolig, men är nu Conjecture 1 (Chen Conjecture). Låt B vara en ändlig relationsstruktur expanderad med alla konstanter. Om Pol(B) har PGP, är QCSP(B) i NP; annars QCSP(B) är Pspacecomplete. I [12], Conjecture 6 ger NP medlemskap och Conjecture 7 Pspace-fullständighet. Vi vet nu från [24] och [7] att NP-medlemskapet i Conjecture 6 verkligen är sant. Det mest intressanta resultatet av denna uppsats är Theorem 1 nedan, men notera att vi tillåter oändliga signaturer (språk) även om våra domäner förblir ändliga. Denna aspekt av vårt arbete kommer att diskuteras i detalj senare. Zhuk har tidigare visat [24] att endast PGP och EGP kan förekomma, även i det icke-idepotenta fallet. Med oändliga språk, NP-medlemskap för Theorem 1 är inte längre omedelbar från [7], men kräver lite extra arbete. Vi kan också vederlägga följande form. Conjecture 2 (Alternativ Chen Conjecture). Låt A vara en idempotent algebra på en ändlig domän A. Om A uppfyller PGP, då för varje ändlig delmängd  till Inv(A), är QCSP( på) i NP. I annat fall finns det en ändlig delmängd  på Inv(A) så att QCSP( ska) är co-NP-hård. Genom att bevisa Theorem 1 säger vi att komplexiteten hos QCSPs, med alla konstanter inkluderade, är klassificerad modulo komplexiteten hos CSPs. På detta sätt följer vårt resultat i fotspåren av det liknande resultatet för den värderade CSP, som också har fått sin komplexitet klassificerad modulo CSP, som kulminerade i tidningen [17]. För en ändlig-domän algebra A associerar vi en funktion f A : N → N, vilket ger kardinaliteten av de minimala generering uppsättningar av sekvensen A, för alla m. Frågan uppstår då om tillväxthastigheten av f och specifikt om beteenden konstant, logaritmiska, linjära, polynomial och exponentiell. Wiegold visade i [23] att om A är en ändlig semigrupp då f A är antingen linjär eller exponentiell, med den förra rådande just när A är en monoid. Denna dikotomiklassificering kan ses som ett gapteorem eftersom ingen tillväxthastighet mellan linjär och exponentiell kan förekomma. Vi säger A har polynomiskt genererade makter egendom (PGP) om det finns en polynom p så att f A = O(p) och exponentiellt genererade makter egendom (EGP) om det finns en konstant b så att f A =  på (g) där Således, en 1, en 2,. .., a k är index där tuple växlar värde. Observera att dessa inte är de ursprungliga definitionerna, som vi snart kommer att se, men de är bevisligen likvärdiga med de ursprungliga definitionerna (åtminstone för finita signaturer) [7]. Dessutom är det dessa definitioner som vi kommer att använda. Vi säger att A är hopfällbar (switchable) om det finns k sådan att det är k-kollapsible (k-switchable). Vi noterar att Zhuk använder denna definition av utbytbarhet i [24] där han bevisade att den enda typen av PGP för finita-domän algebras är utbytbarhet. Låt oss kapitalisera Collapsibility och utbytbarhet för att indikera Chens ursprungliga definitioner från [11] används, enligt ett exempel för aritmetisk kontra Aritmetic av Raymond Smullyan i [22]. Det finns risk för förvirring i början av meningen men, som var fallet med Smullyan, de två kommer att sträva efter att vara utbytbara under hela vårt samtal. Det är enkelt att se att k-Switchability innebär k-switchability och k-Collapsibility innebär k-kollapsibilitet. Konverserna, för finita signaturer, håller också, men detta kräver mer arbete [7]. För varje ändlig algebra innebär k-Collapsibilitet k-Switchability. och för alla 2-element algebra, k-Switchability innebär k-Collapsibility. Chen introducerade ursprungligen utbytbarhet eftersom han hittade en 3-element algebra som gillade PGP men inte var Collapsible [11]. Han fortsatte att bevisa att utbytbarhet av A innebär att motsvarande QCSP är i P, vad man informellt kan säga som QCSP(Inv(A)) i P, där Inv(A) kan ses som strukturen över samma domän som A vars relationer är just de som bevaras av (invariant under) alla operationer av A. Emellertid, QCSP traditionellt definierades endast på ändliga uppsättningar av relationer (eller så uppstår frågan om kodning), alltså en mer formell definition kan vara att, för varje ändlig delmängd av Inv(A), QCSP( ska) är i P. Vad vi bevisar i detta papper är att, vad QCSP är fråga om, Bytbarhet på en tre-element algebra A är något av en hägring. Vad vi menar med detta är att när A kan bytas ut, för alla finita undergrupper av Inv(A), redan Pol( ska) är Collapsible. Därför, för QCSP komplexitet för tre element strukturer, behöver vi inte ytterligare begreppet utbytbarhet för att förklara dragbarhet, eftersom Collapsibility redan kommer att räcka. Eftersom dessa begrepp ursprungligen infördes i samband med QCSP är detta särskilt förvånande. Observera att parametern k av Collapsibility är obunden över dessa ökande finita undergrupper  på samma gång som parametern för utbytbarhet helt klart förblir begränsad. På något sätt föreslår vi att själva utbytbarheten kan ses som ett gränsfenomen för Collapsibility. Vår användning av oändliga språk (dvs. signaturer, eftersom vi arbetar på en ändlig domän) är den enda kontroversiella delen av vårt samtal och förtjänar särskild diskussion. Vi vill hävda att en nödvändig följd av den algebraiska inställningen till (Q)CSP är en försoning med oändliga språk. Det traditionella tillvägagångssättet att överväga godtyckliga finita undergrupper av Inv(A) är otillfredsställande i den meningen att välja detta sätt att fly -naturligt oändligt -set Inv(A) är lika godtyckligt som valet av kodning som krävs för oändliga språk. Men svårigheten i detta val är naturligtvis orsaken till att denna väg ofta är bortkastad. Den första möjligheten som kommer att tänka på för kodning en relation i Inv(A) är förmodligen att lista C V I T 2 0 1 6 23:4 Komplexiteten av kvantifierade begränsningar med hjälp av algebraisk formulering dess tuples, medan den andra är sannolikt att beskriva förhållandet i någon form av "enkel" logik. Båda dessa möjligheter diskuteras i [14], för Booleska domänen, där den "enkla" logiken är propositionskalkylen. För större områden skulle detta motsvara kvantifierfria förslag om jämlikhet med konstanter. Både Conjunktive Normal Form (CNF) och Disjunctive Normal Form (DNF) representationer beaktas i [14] och en liknande diskussion [3] avslöjar fördelarna med DNF-kodningen. Poängen här är att testa non-tomness av en relation kodad i CNF kan redan vara NP-hård, medan för DNF detta kommer att vara dragbar. Eftersom DNF har några godartade egenskaper, kan vi betrakta det som en "fin, enkel" logik medan för "enkel" logik vi omfattar alla kvantifier-fria meningar, som inkluderar DNF och CNF som specialfall. Anledningen till att vi beskriver detta som "enkel" logik är att jämföra mot något starkare, säger alla första ordningens meningar över jämlikhet med konstanter. Här blir icke-tomhet Pspace-hård och eftersom QCSPs redan sitter i Pspace är denna komplexitet orimlig. För QCSP över oändliga språk Inv(A), Chen och Mayr [13] har deklarerat för vår första, tuple-listing, kodning. I detta dokument kommer vi att välja "enkel" logik kodning, ibland ger mer förfinade resultat för sin "fina, enkla" begränsning till DNF. Vårt val av "enkel" logik kodning över tuple-listning kodning kommer i slutändan att motiveras av (Reviderad) Chen Conjecture håller för "enkel" logik men misslyckas med tuple-listningar. Observera att vår demonstration av (Reviderad) Chen Conjecture för oändliga språk med "enkel" logik kodning inte löser den ursprungliga Chen Conjecture för finita språk B med konstanter eftersom QCSP(Inv(Pol(B))) kan tänkas ha högre komplexitet än QCSP(B) på grund av en kortfattad representation av relationer i Inv(Pol(B)). Detta är i själva verket en motivering till den förmånliga studien av finita undergrupper av Inv(Pol(B)), eftersom för finita signatur B kan vi då säga QCSP(B) och QCSP(Inv(PolB)) måste ha samma komplexitet. Observera att för finita relationsbaser B, B av Inv(Pol(B)), QCSP(B ) och QCSP(B ) måste ha samma komplexitet. Vidare känner vi inte till några konkreta finita B med konstanter, så att QCSP(Inv(Pol(B))) och QCSP(B) har olika komplexitet. Låt oss se på några exempel på våra kodningar. För domänen {1, 2, 3} kan vi ge en binär relation antingen genom tuples {(1, 2), (2, 1), (2, 3), (3, 2), (1, 3), (3, 1), (1, 1)} eller genom "enkel" logik formel (x = y  till x = 1). För domänen {0, 1}, kan vi ge den ternära (inte alla-lika) relationen av tuples {(1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, eller av "enkel" logik formel (x = y = z). I båda dessa exempel finns den enkla formeln också i DNF. Inte Bene. Resultaten av detta dokument gäller för "enkel" logikkodning samt "fin, enkel" kodning i DNF om inte annat uttryckligen anges. Dessa undantag är Proposition 2 och Corollary 10 (som använder den "fina, enkla" DNF) och Proposition 4 (som använder tuple kodning). Detta dokument är sammanslagningen av [20, 19], som varken lämnades in för offentliggörande, avsevärt förlängd. Låt [k] := {1,......................................................................................................... En k-är polymorfism av en relationell struktur B är en homomorfism f från B k till B. Låt Pol(B) vara uppsättningen av polymorphisms av B och låt Inv(A) vara uppsättningen av relationer på A som är invariant under (varje av) operationer av någon ändlig algebra A. Pol(B) är ett objekt känt i Universal Algebra som en klon, som är en uppsättning av operationer C. Carvalho et al. som innehåller alla utskjutande delar och som är slutna under sammansättningen (superposition). En term operation av en algebra A är en operation som är en medlem av klonen som genereras av A. Vi kommer att sammanfatta uppsättningar av operationer över samma domän och algebras precis som vi gör uppsättningar av relationer över samma domän och begränsningar språk (relationella strukturer). Den enda tekniska skillnaden mellan sådana föremål är faktiskt förflyttningen bort från en beställd signatur, vilket vi aldrig kommer att behöva. En redukt av en relationsstruktur B är en relationsstruktur B över samma domän som erhålls genom att glömma en del av relationerna. Om  till är någon ändlig delmängd av Inv(A), då kan vi se en varelse en finit redukt av strukturen (associerad med) Inv(A). A Vi kommer ihåg QCSP(B), där B är någon struktur på en ändlig-domän, är ett beslutsproblem med input, en pH-sentens (dvs. genom att använda bara B,  och =) som inbegriper (en ändlig uppsättning av) relationer med B, kodade i propositionslogiken med jämlikhet och konstanter. De ja-instanser är de som B = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 = 0 Om inmatningssatsen är begränsad till att ha växel Π k betecknas motsvarande problem Π k - CSP( B). Vi minns nu en viss terminologi på grund av Chen [9, 11], för hans naturliga anpassning av modellen kontroll spelet till sammanhanget av pH-effekter. Vi behöver inte uttryckligen spela dessa spel utan bara hantera strategier för den existentiella spelaren. Detta kommer att göra det möjligt för oss att ge de ursprungliga definitionerna för Collapsibility och Switchability. En motståndare B av längd m ≥ 1 är en m-är relation över A. När B är exakt den inställda B 1 × B 2 ×. .. × B m för vissa icke-tomma undergrupper B 1, B 2,. .., B m av A, vi talar om en rektangulär motståndare (vi kommer ibland ange detta som en tuple snarare än en produkt). Låta vara en pH-entens med universella variabler x 1,. .., x m och kvantifier-fri del  och......, x m och kvantifier-fri del Vi skriver A  på B och säger att den existentiella spelaren har en vinnande strategi i (A,  och)-spelet mot motståndaren B if det finns en uppsättning av Skolem funktioner {σ x : : " påx"  på så sätt att för varje uppdrag π av de universellt kvantifierade variablerna i A, där π(x 1 ),. ., π(x m ) B, kartan h π är en homomorfism från D  och (den kanoniska databasen) till A, där, Om x är en universell variabel; och (Här, Y x betecknar uppsättningen universella variabler före x och π på Yx begränsningen av π till Y x.) Det är tydligt att en existentiell spelare har en vinnande strategi i spelet mot den så kallade fullständiga (rektangulära) motståndaren A × A ×. .. × A (som vi kommer att beteckna nedan med A m ). Vi säger att en motståndare B av längd m dominerar en motståndare B av längd m när B  på B. Observera att B och A = B innebär A = B. Vi kommer också att överväga uppsättningar av motståndare av samma längd, betecknad med stora grekiska bokstäver som i M (här är längden m); och, sekvenser därav, som vi betecknar med djärva stora grekiska bokstäver som i  och = M m på N. Vi kommer att skriva A  på ett sätt som betecknar att A  och B håller för varje motståndare B i m. Låt f vara en k-ary drift av A och A, B 1,. .., B k vara motståndare av längd m. Vi säger att A är reaktivt kompatibel från motståndaren B 1,. .., B k via f, och vi skriver A f (B 1,. .., B k ) if det finns partiella funktioner g Komplexiteten av kvantifierade begränsningar med hjälp av algebraisk formulering för varje j i [k], värdena g a 2 ). Reaktiv komposition spelar en nyckelroll i beviset på vår huvudsats, men dess användning förekommer bara i andra papper som vi kommer att citera. Vanlig sammansättning är den enda typen av reaktiv sammansättning som kommer att användas i detta dokument. Chen Conjecture Vi måste se över huvudresultatet av [7] för att visa att det inte bara gäller finita signaturer utan även oändliga signaturer. I sitt original diskuterade följande teorem "projektiva sekvenser av motståndare, av vilka ingen är degenererade". Detta inkluderar Byta motståndare och vi ger det i denna senare form. Vi tar dessutom bort vissa delar av teorem som för närvarande inte är relevanta för oss. (i ) (i) (i)) Genom kontraposition, om (i) misslyckas då det misslyckas på vissa specifika pH-sentens som bara nämner ett begränsat antal relationer av A. Således (i ) misslyckas också på några finita redukt av A nämner dessa relationer. [(vi ) Vi m. Observera att i (vi ) Vi ovan vi inte behövde argumentera enhetligt över olika (a 1,. ., en m ) och det är tillräckligt för att hitta en oändligt återkommande operation för var och en av dessa individuellt. Följande resultat är i huvudsak en följd av Chen och Zhuks verk [11, 24] via [7]. Bevis. Vi vet från Theorem 7 i [24] att A är utbytbar, varpå vi tillämpar Corollary 5, (vi)  på (i). Genom att överväga fall vars universella variabler endast omfattar polynomet antal tuples från Switching Adversary, kan man se att QCSP(Inv(A)) minskar till ett polynom antal fall av CSP(Inv(A)) och är därför i NP. Ytterligare detaljer om NP-algoritmen ges i Corrollary 38 av [7], men argumentet här följer exakt avsnitt 7 från [11], där det ursprungligen bevisats att utbytbarhet ger motsvarande QCSP i NP. Observera att Chens ursprungliga definition av utbytbarhet, baserad på motståndare och reaktiv kompatibilitet, spelar en nyckelroll i NP-medlemskapsalgoritmen i Theorem 6. Det är resultatet av [7] som krävs för att sammanjämka de två definitionerna av utbytbarhet som ekvivalent, och det krävs i denna process för oändliga signaturer. Om vi bara skulle använda vår definition av utbytbarhet är det bara möjligt att bevisa, à la Proposition 3.3 in [11], att den avgränsade alterneringen Π n -CSP(Inv(A)) är i NP. Med hjälp av bara metoderna från [11] och [24] kan vi alltså inte bevisa den reviderade Chen Conjecture, utan snarare några avgränsade alternation (om)revision. Antag att det finns α, β strikta undergrupper av A så att α  och β = A, definiera förhållandet Strikt talat, α och β är parametrar av τ k men vi avstår från att lägga till dem till notationen eftersom de kommer att fastställas vid någon punkt C V I T 2 0 1 6 23:8 Komplexiteten av kvantifierade begränsningar med hjälp av algebraisk formulering där vi åberopar τ k. Syftet med förbindelserna τ k är att koda co-NP-hårdhet genom komplementet till problemet (monoton) 3-inte-all-lika-tillfredsställelse (3 NAESAT). Låt oss också införa de viktiga förbindelserna σ k (x 1, y 1 Bevis. Vi kommer att hävda att τ k är definierbar genom den sammantagna 0 av 3 k fall av σ k att varje överväga de sätt på vilka två variabler kan väljas från var och en av de ( där  till är infix för ρ). Vi måste visa att denna förbindelse 0 innebär τ k (konversationen är trivial). Vi utgår från att 0 är tillfredsställande, men inte τ k. I det första fallet av σ k av 0 någon atom måste vara sant, och det kommer att vara av formen x i  på y i eller y i z i eller x i z i. När vi har slagit oss till ro med en av dessa tre, p i  ska q i, då uppfyller vi omedelbart 3 k-1 i samband med 0, vilket lämnar 2 · 3 k-1 otillfredsställda. Nu, kan vi inte utvärdera sant någon av de andra bland motsäger vårt antagande. Således är vi nu ner till att titta på variabler med andra subscript än i och på detta sätt har vi gjort utrymmet en mindre, totalt k − 1. Nu kommer vi att behöva utvärdera i 0 någon annan atom av blanketten x j och y j z j eller x j z j, för j = i. När vi väl har slagit oss ner på en av dessa tre så uppfyller vi omedelbart 2 · 3 k−2 av de förbindelser som återstår av 0, vilket lämnar 2 2 · 3 k−2 fortfarande otillfredsställda. Itering av detta tänkande, vi kommer fram till en situation där 2 k klausuler är otillfredsställda efter att vi har gått igenom alla k underskrifter, vilket är en motsägelse. Bevis. Vi vet från Lemma 11 i [24] att det finns α, β stränga undergrupper av A så att α  till β = A och förhållandet σ k är i Inv(A), för varje k  till N. Från Lemma 7, vi vet också att τ k är i Inv(A), för varje k  till N. Vi kommer härnäst att hävda att τ k har en relativt liten specifikation i DNF (åtminstone polynomial i k). Vi ger först en sådan specifikation för ρ (x, y, z). som är konstant i storlek när A är fast. Nu framgår det tydligt av definitionen att storleken på τ n är polynom i n. Vi kommer nu att ge en mycket enkel minskning från komplement av 3NAESAT till QCSP(Inv(A)). 3NAESAT är välkänt för att vara NP-fullständig [21] och vårt resultat kommer att följa. Till exempel 3NAESAT som är den existentiella kvantifieringen av en förening av k atomer NAE (x, y, z). Således är den universella kvantifieringen av en diskontering av k atomer x = y = z. Vi bygger vår instans av QCSP(Inv(A)) från ¬en genom att omvandla den kvantifier-fria delen (¬entreprenaden av QCSP (Inv(A))).) Från en tilldelning till de universella variablerna v 1,. .., v m av  på element x 1,. .., x m av A, överväga element x 1,. .., x m  till {0, 1} enligt, och x i  till  och β innebär att vi inte bryr oss, så w.l.o.g. Säg x i = 0. C. Carvalho m.fl. Den disjunkt som är nöjd i den kvantifier-fria delen av ¬ på ger nu motsvarande disjunkt som kommer att vara nöjd i τ k. ( ska QCSP(Inv(A)) innebär ¬ på co-3NAESAT.) Från en tilldelning till de universella variablerna v 1,. .., v m av ¬ på element x 1,. .., x m av {0, 1}, överväga element x 1,. ., x m A enligt x i = 0 innebär x i är något godtyckligt valt element i α\ β, och x i = 1 innebär x i är någon godtyckligt valt element i β\ α. Den disjunkt som är nöjd i τ k ger nu motsvarande disjunkt som kommer att vara nöjd i den kvantifier-fria delen av ¬. Demonstrationen av co-NP-hårdhet i det tidigare teorem inspirerades av ett liknande bevis [2]. Observera att ett alternativt bevis på att τ k är i Inv(A) läggs fram genom observationen att den bevaras av alla αβ-projektioner (se [24]). Vi noterar överraskande att co-NP-hårdhet i Theorem 8 är optimal, i den meningen att vissa (men inte alla!) av de ärenden som just inletts med NP-hårda är också i co-NP. Förslag 1. Låt α, β stränga undergrupper av A := {a 1,. .., a n } så att α  och β = ∅. Sedan QCSP( A; {τ k: k  på N}, en 1,. ., a n ) är i co-NP. Bevis. Antag att det rör sig om > 1, d.v.s. n > 1 (observera att beviset annars är trivialt). Låta vara en ingång till QCSP(A; {τ k: k  på N}, en 1,. .., a n )......................................................................................................... Vi kommer nu att försöka eliminera atomer v = a (a) {a 1,. .., a n }) från........ )...................... )........................................................................ Antag att den har en atom v = a. Om v är universellt kvantifierad, då är osann (sedan  och A) > 1). Annars, antingen atomen v = a kan elimineras med variabeln v eftersom v inte visas i en icke-jämlikhet förhållande; eller  och är falskt eftersom det finns en annan atom v = a för a = a ; eller v = en kan tas bort genom att ersätta en i alla icke-jämlikhet fall av relationer som involverar v. Detta förbehandlingsförfarande är polynomial och vi kommer att anta w.l.o.g. som inte innehåller några atomer v = a. Vi hävdar nu att "ja-instans iff" är en "ja-instans", där man bygger från "en" genom att direktimera alla existentiellt kvantifierade variabler som vilken som helst "α" β. Den universella kan utvärderas i co-NP (man kan föredra att föreställa sig komplementet som en existentiell ¬ på att utvärderas i NP) och resultatet följer. Faktum är, att detta är en algebraisk tidning, vi kan till och med göra bättre. Låt B betyda en uppsättning relationer på en ändlig domän men inte nödvändigtvis sig själv ändlig. För enkelhetens skull, kommer vi att anta att uppsättningen av relationer av B är stängd under alla koordinat projektioner och momentiationer av konstanter. Ring B existentiellt trivialt om det finns ett element c  till B (som vi kallar en kanon) sådan att för varje k-ary relation R av B och varje i k, och för varje x 1,. .., x k  till B, när (x 1,.................................................................................... .., Vi vill expandera denna klass till nästan existentiellt triviala genom att tillåta samband av formen v = a i eller v = v med relationer som är existentiellt triviala. - Lemma 9. - Vad är det? Låt α, β vara strikta undergrupper av A := {a 1,. .., a n } så att α  och β = ∅. Den uppsättning förbindelser pp-definierbar i (A; {τ k: k  på N}, a 1,. .., a n ) är nästan existentiellt trivial. Bevis. Överväg en formel med en pp-definition i (A; {τ k: k  på N}, en 1,. .., a n )......................................................................................................... Vi antar att endast fria variabler visas i lika villkor eftersom vi annars kan ta bort dessa lika värden genom substitution. Nu existentiella kvantifieringar kan tas bort och deras variabler omedelbart som kanon c. I själva verket, deras atomer τ n kan nu tas bort eftersom de alltid kommer att vara nöjda. Således är vi kvar med en förening av jämlikhet och atomer τ n, och resultatet följer. Komplexiteten av kvantifierade begränsningar med hjälp av algebraisk formulering Bevis. Argumentet här är ganska lik det i Proposition 1 förutom att det finns några ytterligare förbehandling för att ta reda på variabler som är tvingade i någon relation till att vara en enda konstant eller par av variabler i ett förhållande som är tvungna att vara lika. I det första fallet att någon variabel är tvungen att vara konstant i ett k-ary förhållande, bör vi ersätta med (k - 1)-är relationen med den nödvändiga tvingar. I det andra fallet att ett par variabler tvingas lika då ersätter vi återigen k-ary relationen med en (k − 1)-är relation samt en jämställdhet. Observera att projicering en relation till en enda eller två koordinater kan göras i polynom tid eftersom relationerna är kodade i DNF. Efter att ha följt dessa regler till sin slutsats får man en förening av jämlikheter tillsammans med relationer som är existentiellt triviala. Nu är det dags att sprida variabler för att ta bort jämlikheter (eller finna att det inte finns någon lösning). Slutligen, när endast existentiellt triviala relationer återstår, kan alla återstående existentiella variabler utvärderas till kanon c. Corollary 10. Låt α, β vara strikta undergrupper av A := {a 1,. .., a n } så att α  och β = ∅. Sedan QCSP(Inv(Pol(A; {τ k : k  på N}, a,. ., a n ))) är i co-NP under DNF-kodning. Detta sista resultat, tillsammans med dess stödjande förslag, är den enda gången vi verkar kräva den "fina, enkla" DNF-kodning, snarare än godtyckliga förslagslogik. Vi kräver inte DNF för Proposition 1 eftersom vi bara har en enda relation i signaturen för varje arity och detta är lätt att hålla reda på. Vi noterar att uppsättningen av relationer {τ k: k  på N} inte är maximal med egendomen som med konstanterna den bildar en co-clone av existentiellt triviala relationer. Man kan till exempel lägga till α × β  och β × α. Följande, tillsammans med våra tidigare resultat, ger vederläggning av Alternativ Chen Conjecture. Förslag 3. Låt α, β stränga undergrupper av A := {a 1,. .., a n } så att α  och β = ∅. Därefter, för varje ändlig signatur redukt B av (A; {τ k: k  på N}, en 1,. .., a n ), QCSP(B) är i NL. Bevis. Vi kommer att anta att B innehåller alla konstanter (eftersom vi bevisar att detta fall ger en QCSP i NL, följer det naturligtvis att samma innehar utan konstanter). Ta m så att, för varje τ i B, i ≤ m. Kom ihåg från Lemma 7 att τ i är pp-definierbar i σ i. Vi kommer att bevisa att strukturen B ges av (A; {σ k : k ≤ m}, en 1,. ., a n ) medger en (3m + 1)-är nära-enighet operation f som en polymorfism, varpå det följer att B medger samma nära-enighet polymorfism. Vi väljer f så att alla tupler vars karta inte automatiskt definieras av nästan enhällighetskriteriet karta till någon godtycklig en. För att se detta, föreställ dig att detta f inte var en polymorfism. Sedan några (3m + 1) tuples i σ i skulle kartläggas till någon tuple inte i σ i som måste vara en tuple t av element från α\ β  ska β \ α. Observera att denna karta endast kan komma från (3m + 1)-tupler som har 3m fall av samma element. Enligt duvhålsprincipen måste tuple t visas som en av de (3m + 1) tuples i σ i och detta är helt klart en motsägelse. Det följer av [9] att QCSP(B) minskar till en polynomiskt avgränsad ensemble av n 3m · n · n 3m fall CSP(B), och resultatet följer. Förslag 4. Låt α := {0, 1} och β := {0, 2}. Därefter är QCSP( {0, 1, 2}; {τ k: k  på N}, 0, 1, 2) i P under tupelkodningen. Bevis. Betrakta ett exempel på denna QCSP av storlek n som omfattar relationen τ m men ingen relation τ k för k > m. Antalet tuples i τ m är > 3 m. Efter Proposition 1 tillsammans med dess C. Carvalho et al. bevis, kan vi anta att fallet är strikt universellt kvantifieras över en förening av atomer (inklusive även konstanter). Nu är ett universellt kvantifierat samband sant om dess universellt kvantifierade atomers förening är sann. Vi kan vidare säga att det finns som mest n atomer som vart och ett omfattar högst 3m variabler. Därför finns det en uttömmande algoritm som tar högst O(n · 3 3m ) steg med är O(n 4).
I REF har vi visat en variant av Chen Conjecture med hjälp av oändliga relationsspråk kodade i kvantifier-fri logik med konstanter och jämlikhet.
The Complexity of Quantified Constraints Using the Algebraic Formulation
{'venue': 'MFCS', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}