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. Considera (x ∨ y) ∧ (¬x ∨ y) ∧ (x ∨ ¬y). Ogni clausola ha due letterali. — 1. Leggi le clausole
Considera $(x \lor y) \land (\neg x \lor y) \land (x \lor \neg y)$ . Ogni clausola ha due letterali.

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}}$

$\htmlData{term=problem:SAT2}{\mathrm{2\text{-}SAT}} \in \htmlData{term=P}{\mathrm{P}}$ 2-SAT è P-completo se e solo se $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NL}{\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 $\htmlData{term=Π2}{\Pi_2^{\mathrm{P}}} = \htmlData{term=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.

Problemi del corso

1. Leggi le clausole

2. Trova i valori coerenti

3. Verifica tutte le clausole