Problemi del corso

Scegli un problema, segui l'esempio illustrato e passa al prossimo.

ClasseSolo completiSolo nelle tracce

36 problemi

Problema 2 di 36

2-SAT

Formula in forma normale congiuntiva (CNF) in cui ogni clausola ha al più 2 letterali: è soddisfacibile?

NLNL-completo

Nelle tracce · 5 domande

F01, domanda 7 F06, domanda 2 G17, domanda 2 GE23, domanda 3 MA23, domanda 1

Un esempio, passo dopo passo

1 / 3

Leggi le clausole. I tre riquadri sono le clausole di (x ∨ y) ∧ (¬ x ∨ y) ∧ (x ∨ ¬ y), scritte con OR e NOT, e ognuna ha due letterali. Gli interruttori sotto servono a scegliere i valori di x e y. — 1. Leggi le clausole
I tre riquadri sono le clausole di $(x \lor y) \land (\neg x \lor y) \land (x \lor \neg y)$ , scritte con OR e NOT, e ognuna ha due letterali. Gli interruttori sotto servono a scegliere i valori di $x$ e $y$ .

Trova i valori coerenti. La seconda clausola equivale a x ⇒ y e la terza a y ⇒ x: sono le due frecce fra gli interruttori, archi del grafo delle implicazioni, e obbligano x e y ad avere lo stesso valore. La coppia di interruttori spenti, barrata in rosso, è x = y = 0, esclusa dalla prima clausola. Resta x = y = 1, i due interruttori verdi. — 2. Trova i valori coerenti
La seconda clausola equivale a $x \Rightarrow y$ e la terza a $y \Rightarrow x$ : sono le due frecce fra gli interruttori, archi del grafo delle implicazioni, e obbligano $x$ e $y$ ad avere lo stesso valore. La coppia di interruttori spenti, barrata in rosso, è $x = y = 0$ , esclusa dalla prima clausola. Resta $x = y = 1$ , i due interruttori verdi.

Scorri l'immagine o usa Avanti.

Ogni clausola $a \lor b$ equivale alle implicazioni $\neg a \Rightarrow b$ e $\neg b \Rightarrow a$ . La formula è insoddisfacibile esattamente quando una variabile e la sua negazione appartengono alla stessa componente fortemente connessa del grafo delle implicazioni. Il problema si risolve in tempo polinomiale ed è decidibile in spazio logaritmico nondeterministico.

Complemento e collegamenti

Il complemento (2-CNF insoddisfacibili) sta in

\mathrm{coNL} = \htmlData{term=NL}{\mathrm{NL}}

, quindi è anch'esso NL-completo.

2 contro 3 letterali: NL-completo contro NP-completo
stesse clausole da 2 letterali, ma "almeno $K$ vere" è NP-completo
2-SAT si decide cercando cammini nel grafo delle implicazioni
due restrizioni di SAT che diventano facili
PRIMES → 2-SAT solo se $\htmlData{term=problem:PRIMES}{\mathrm{PRIMES}} \in \htmlData{term=NL}{\mathrm{NL}}$

$\mathrm{2\text{-}SAT} \in \mathrm{P}$ 2-SAT è P-completo se e solo se $\mathrm{P} = \mathrm{NL}$

Domande e trappole d'esame

F01#7
È vero che 2-SAT non appartiene a DP?
NO $\htmlData{term=problem:SAT2}{\mathrm{2\text{-}SAT}} \in \htmlData{term=NL}{\mathrm{NL}} \subseteq \htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=NP}{\mathrm{NP}} \subseteq \htmlData{term=DP}{\mathrm{DP}}$ .
F06#2
Esiste una riduzione da $\mathrm{co\text{-}QSAT}_2$ a 2-SAT?
altro: solo se $\Pi_2^{\mathrm{P}} = \mathrm{P}$ $\mathrm{co\text{-}QSAT}_2$ è $\htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}$ -completo e 2-SAT sta in P: la riduzione porterebbe $\htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}$ in P, e PH collasserebbe a P.
GE23#3
GEOGRAPHY è riducibile a 2-SAT?
NOGEOGRAPHY è PSPACE-completo e $\htmlData{term=problem:SAT2}{\mathrm{2\text{-}SAT}} \in \htmlData{term=NL}{\mathrm{NL}}$ : avremmo $\htmlData{term=PSPACE}{\mathrm{PSPACE}} \subseteq \htmlData{term=NL}{\mathrm{NL}}$ , contro $\htmlData{term=NL}{\mathrm{NL}} \subsetneq \htmlData{term=PSPACE}{\mathrm{PSPACE}}$ .
G17#2
Supponiamo $\htmlData{term=P}{\mathrm{P}} \subset \htmlData{term=Σ3}{\Sigma_3^{\mathrm{P}}}$ . È vero che 2-SAT non è $\htmlData{term=Σ3}{\Sigma_3^{\mathrm{P}}}$ -completo?
SÌSe lo fosse, $\htmlData{term=Σ3}{\Sigma_3^{\mathrm{P}}} \subseteq \htmlData{term=P}{\mathrm{P}}$ , contro l'ipotesi.
PRIMES si riduce a 2-SAT in spazio logaritmico se e solo se $\htmlData{term=problem:PRIMES}{\mathrm{PRIMES}} \in \htmlData{term=NL}{\mathrm{NL}}$ , perché 2-SAT è NL-completo.