Problemi del corso

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

ClasseSolo completiSolo nelle tracce

36 problemi

Problema 9 di 36

3-SAT

SAT in cui ogni clausola ha al più 3 letterali.

NPNP-completo

Nelle tracce · 1 domande

F03, domanda 3

Un esempio, passo dopo passo

1 / 3

Conta i letterali. I due riquadri sono le clausole di (x ∨ y ∨ z) ∧ (¬ x ∨ y ∨ ¬ z). Ogni cerchio è un letterale e ogni riquadro ne contiene tre, come chiede 3-SAT. La formula è vera se in ogni riquadro almeno un cerchio è vero. — 1. Conta i letterali
I due riquadri sono le clausole di $(x \lor y \lor z) \land (\neg x \lor y \lor \neg z)$ . Ogni cerchio è un letterale e ogni riquadro ne contiene tre, come chiede 3-SAT. La formula è vera se in ogni riquadro almeno un cerchio è vero.

Scorri l'immagine o usa Avanti.

Un assegnamento si verifica come per SAT. Introducendo variabili ausiliarie, una clausola lunga si trasforma in clausole con al più tre letterali preservando la soddisfacibilità, quindi la restrizione a tre letterali mantiene la difficoltà di SAT.

Complemento e collegamenti

Nessun complemento associato.

2 contro 3 letterali: NL-completo contro NP-completo
SAT si riduce a 3-SAT spezzando le clausole
3-SAT si riduce a 3-COL
3-SAT si riduce a INDEPENDENT SET

3-SAT è NP-completo

Domande e trappole d'esame

F03#3
$\htmlData{term=problem:SAT3}{\mathrm{3\text{-}SAT}} \in \htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}$ ?
SÌ $\htmlData{term=problem:SAT3}{\mathrm{3\text{-}SAT}} \in \htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=Σ1}{\Sigma_1^{\mathrm{P}}} \subseteq \htmlData{term=Δ2}{\Delta_2^{\mathrm{P}}} \subseteq \htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}$ .
Il salto da 2 a 3 letterali: 2-SAT sta in NL, 3-SAT è NP-completo.

Problemi del corso

1. Conta i letterali

2. Scegli il certificato

3. Controlla tutte le clausole