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. Considera (x ∨ y ∨ z) ∧ (¬x ∨ y ∨ ¬z): ogni clausola ha tre letterali. — 1. Conta i letterali
Considera $(x \lor y \lor z) \land (\neg x \lor y \lor \neg z)$ : ogni clausola ha tre letterali.

Scorri l'immagine o usa Avanti.

Un assegnamento si verifica come per SAT. Una clausola lunga si può trasformare in clausole con al più tre letterali introducendo variabili ausiliarie e preservando la soddisfacibilità. La restrizione a tre letterali mantiene quindi 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