Teorema di dicotomia di Schaefer

Il teorema di dicotomia di Schaefer Nella teoria della complessità computazionale, una branca dell'informatica, Il teorema di dicotomia di Schaefer afferma condizioni necessarie e sufficienti in cui un insieme finito S di relazioni sul dominio booleano produce problemi di tempo polinomiale o NP-completi quando le relazioni di S vengono utilizzate per vincolare alcune delle variabili proposizionali.[1] È chiamato teorema di dicotomia perché la complessità del problema definito da S è in P o NP-completo rispetto a una delle classi di complessità intermedia che è nota l'esistenza (assumendo P ≠ NP) dal teorema di Ladner.

Casi speciali del teorema di dicotomia di Schaefer includono la NP-completezza di SAT (il problema della soddisfacibilità booleana) e le sue due popolari varianti 1-in-3 SAT e 3SAT non tutti uguali (spesso indicato con NAE-3SAT). Infatti, per queste due varianti di SAT, Il teorema di dicotomia di Schaefer mostra che le loro versioni monotone (dove non sono ammesse negazioni di variabili) sono anche NP-completi.

Contenuti 1 Presentazione originale 2 Presentazione moderna 3 Proprietà dei polimorfismi 4 generalizzazioni 5 Lavoro correlato 6 Guarda anche 7 References Original presentation Schaefer defines a decision problem that he calls the Generalized Satisfiability problem for S (indicato con SAT(S)), dove {stile di visualizzazione S={R_{1},ldot ,R_{m}}} è un insieme finito di relazioni su variabili proposizionali. Un esempio del problema è una formula S, cioè. una congiunzione di vincoli della forma {stile di visualizzazione R_{j}(X_{io_{1}},ldot ,X_{io_{n}})} dove {stile di visualizzazione R_{j}a s} e il {stile di visualizzazione x_{io_{j}}} sono variabili proposizionali. Il problema è determinare se la formula data è soddisfacente, in altre parole se alle variabili possono essere assegnati valori tali da soddisfare tutti i vincoli dati dalle relazioni di S.

Schaefer identifica sei classi di insiemi di relazioni booleane per le quali SAT(S) è in P e dimostra che tutti gli altri insiemi di relazioni generano un problema NP-completo. Un insieme finito di relazioni S sul dominio booleano definisce un problema di soddisfacibilità calcolabile in tempo polinomiale se vale una qualsiasi delle seguenti condizioni: tutte le relazioni che non sono costantemente false sono vere quando tutti i suoi argomenti sono veri; tutte le relazioni che non sono costantemente false sono vere quando tutti i suoi argomenti sono falsi; tutte le relazioni sono equivalenti a una congiunzione di clausole binarie; tutte le relazioni sono equivalenti a una congiunzione di clausole di Horn; tutte le relazioni sono equivalenti a una congiunzione di clausole dual-horn; tutte le relazioni sono equivalenti a una congiunzione di formule affini. [2] Altrimenti, il problema SAT(S) è NP-completo.

Modern presentation A modern, una presentazione semplificata del teorema di Schaefer è data in un documento espositivo di Hubie Chen.[3][4] In termini moderni, il problema SAT(S) è visto come un problema di soddisfazione dei vincoli sul dominio booleano. In quest 'area, è standard denotare l'insieme delle relazioni con Γ e il problema decisionale definito da Γ come CSP(C).

Questa comprensione moderna usa l'algebra, in particolare, algebra universale. Per il teorema di dicotomia di Schaefer, il concetto più importante nell'algebra universale è quello di un polimorfismo. Un'operazione {stile di visualizzazione f:D^{m}a D} è un polimorfismo di una relazione {displaystyle Rsubseteq D^{K}} Se, per qualsiasi scelta di m tuple {stile di visualizzazione (t_{11},punti ,t_{1K}),punti ,(t_{m1},punti ,t_{mk})} da R, sostiene che la tupla ottenuta da queste m tuple applicando f in base alle coordinate, cioè. {stile di visualizzazione (f(t_{11},punti ,t_{m1}),punti ,f(t_{1K},punti ,t_{mk}))} , è in R. Questo è, un'operazione f è un polimorfismo di R se R è chiuso sotto f: applicando f a qualsiasi tupla in R si ottiene un'altra tupla all'interno di R. Si dice che un insieme di relazioni Γ ha un polimorfismo f se ogni relazione in Γ ha f come polimorfismo. Questa definizione consente la formulazione algebrica del teorema di dicotomia di Schaefer.

Sia Γ un linguaggio a vincolo finito sul dominio booleano. Il problema CSP(C) è decidibile in tempo polinomiale se Γ ha una delle seguenti sei operazioni come polimorfismo: l'operazione unaria costante 0; l'operazione unaria costante 1; l'operazione AND binaria ∧; l'operazione OR binaria ∨; l'operazione a maggioranza ternaria {nome dell'operatore dello stile di visualizzazione {Maggioranza} (X,y,z)=(xcuneo y)v (xcuneo z)v (ywedge z);} l'operazione di minoranza ternaria {nome dell'operatore dello stile di visualizzazione {Minoranza} (X,y,z)=xoplus yoplus z.} Altrimenti, il problema CSP(C) è NP-completo.

In questa formulazione, è facile verificare se sussiste qualche condizione di trattabilità.

Properties of Polymorphisms Given a set Γ of relations, c'è una connessione sorprendentemente stretta tra i suoi polimorfismi e la complessità computazionale di CSP(C).

Una relazione R è detta primitiva definibile positiva, o breve pp-definibile, da un insieme Γ di relazioni se R(v1, ... , vk) ⇔ ∃x1 ... xm. C vale per qualche congiunzione C di vincoli da Γ ed equazioni sulle variabili {v1,...,vk, x1,...,xm}. Per esempio, se Γ è costituito dalla relazione ternaria nae(X,y,z) tenendo se x,y,z non sono tutti uguali, e R(X,y,z) è x∨y∨z, allora R può essere definito in pp da R(X,y,z) ⇔ ∃a. no(0,X,un) ∧ n.a(y,z,¬a); questa riduzione è stata utilizzata per dimostrare che NAE-3SAT è NP-completo. L'insieme di tutte le relazioni che sono pp-definibili da Γ è indicato con ≪Γ≫. Se Γ' ⊆ ≪Γ≫ per qualche vincolo finito insiemi Γ e Γ', poi CSP(C') si riduce a CSP(C).[5] Dato un insieme Γ di relazioni, Pol(C) denota l'insieme dei polimorfismi di Γ. al contrario, se O è un insieme di operazioni, poi inv(o) denota l'insieme di relazioni che hanno tutte le operazioni in O come un polimorfismo. Pol e Inv insieme creano una connessione Galois. Per ogni insieme finito Γ di relazioni su un dominio finito, ≪Γ≫ = Inv(Pol(C)) tiene, questo è, l'insieme delle relazioni pp-definibili da Γ può essere derivato dai polimorfismi di Γ.[6] Inoltre, se il pol(C) ⊆ Pol(C') per due insiemi di relazioni finite Γ e Γ', quindi Γ' ⊆ ≪Γ≫ e CSP(C') si riduce a CSP(C). Come conseguenza, due insiemi di relazioni aventi gli stessi polimorfismi portano alla stessa complessità computazionale.[7] Generalizations The analysis was later fine-tuned: CSP(C) è risolvibile in co-NLOGTIME, L-completo, NL-completo, ⊕L-completo, P-completo o NP-completo e dato Γ, si può decidere in tempo polinomiale quale di questi casi vale.[8] Il teorema di dicotomia di Schaefer è stato recentemente generalizzato a una classe più ampia di relazioni.[9] Related work If the problem is to count the number of solutions, che è indicato da #CSP(C), quindi vale un risultato simile di Creignou e Hermann.[10] Sia Γ un linguaggio a vincolo finito sul dominio booleano. Il problema #CSP(C) è calcolabile in tempo polinomiale se Γ ha un'operazione di Mal'tsev come polimorfismo. Altrimenti, il problema #CSP(C) è #P-completo. Un'operazione di Mal'tsev m è un'operazione ternaria che soddisfa {stile di visualizzazione m(X,y,y)= m(y,y,X)=x.} Un esempio di operazione di Mal'tsev è l'operazione di minoranza data nel moderno, formulazione algebrica del teorema di dicotomia di Schaefer sopra. così, quando Γ ha l'operazione di Minoranza come polimorfismo, non è solo possibile decidere CSP(C) in tempo polinomiale, ma per calcolare #CSP(C) in tempo polinomiale. Ci sono un totale di 4 Operazioni di Mal'tsev su variabili booleane, determinato dai valori di {stile di visualizzazione m(T,F,T)} e {stile di visualizzazione m(F,T,F)} . Un esempio di uno meno simmetrico è dato da {stile di visualizzazione m(X,y,z)=(xcuneo z)v (neg ywedge (xvee z))} . Su altri domini, come i gruppi, esempi di operazioni Mal'tsev includono {stile di visualizzazione x-y+z} e {stile di visualizzazione xy^{-1}z.} Per domini più grandi, anche per un dominio di dimensione tre, l'esistenza di un polimorfismo di Mal'tsev per Γ non è più condizione sufficiente per la trattabilità di #CSP(C). Tuttavia, l'assenza di un polimorfismo di Mal'tsev per Γ implica ancora la durezza #P di #CSP(C).

Vedi anche Teoremi di classificazione Max/min CSP/Ones, un insieme simile di vincoli per problemi di ottimizzazione Riferimenti ^ Schaefer, Thomas J. (1978). "La complessità dei problemi di soddisfacibilità". SCORTA 1978. pp. 216–226. doi:10.1145/800133.804350. ^ Schäfer (1978, p.218 a sinistra) definisce una formula affine come x1 ⊕ ... ⊕ xn = c, dove ogni xi è una variabile, c è una costante, cioè. vero o falso, e "⊕" denota XOR, cioè. aggiunta in un anello booleano. ^ Chen, Hubie (Dicembre 2009). "Un appuntamento di logica, Complessità, e Algebra". Indagini informatiche ACM. 42 (1): 1–32. arXiv:cs/0611018. doi:10.1145/1592451.1592453. ^ Chen, Hubie (Dicembre 2006). "Un appuntamento di logica, Complessità, e Algebra". Notizie SIGACT (Colonna logica). arXiv:cs/0611018. ^ Chen (2006), p.8, Proposizione 3.9; Chen usa la riduzione multi-uno a tempo polinomiale ^ Chen (2006), p.9, Teorema 3.13 ^ Chen (2006), p.11, Teorema 3.15 ^ Allender, Eric; terreno edificabile, Michael; Immerman, Neil; Schnoor, Henning; Volmer, Eriberto (Giugno 2009). "La complessità dei problemi di soddisfacibilità: Affinamento del teorema di Schaefer" (PDF). Giornale di scienze informatiche e dei sistemi. 75 (4): 245–254. doi:10.1016/j.jcss.2008.11.001. Recuperato 2013-09-19. ^ Bodirsky, Manuele; Pentecoste, Michael (2015). "Teorema di Schaefer per i grafi". J. ACM. 62 (3): 19:1–19:52. arXiv:1011.2894. doi:10.1145/2764899. ^ Creigno, Nadia; Hermann, Miki (1996). "Complessità dei problemi di conteggio della soddisfacibilità generalizzata". Informazione e calcolo. 125 (1): 1–12. doi:10.1006/inco.1996.0016. ISSN 0890-5401. Categorie: Programmazione dei vincoli Teoremi nella teoria della complessità computazionale

Se vuoi conoscere altri articoli simili a Teorema di dicotomia di Schaefer puoi visitare la categoria Constraint programming.

lascia un commento

L'indirizzo email non verrà pubblicato.

Vai su

Utilizziamo cookie propri e di terze parti per migliorare l'esperienza dell'utente Maggiori informazioni