Problemi del corso

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

ClasseSolo completiSolo nelle tracce

36 problemi

Problema 8 di 36

SAT

Data una formula booleana in CNF: esiste un assegnamento delle variabili che la rende vera?

NPNP-completo

Nelle tracce · 5 domande

F08, domanda 8 G16, domanda 8 FE23, domanda 2 E26, domanda 8 ND, domanda 8

Un esempio, passo dopo passo

1 / 3

Leggi l'istanza. I tre riquadri sono le clausole di (x ∨ y) ∧ (¬ x ∨ z) ∧ (¬ y ∨ ¬ z), scritte con OR e NOT. La formula è vera solo se lo sono tutte e tre. Gli interruttori sotto servono a scegliere i valori di x, y e z. — 1. Leggi l'istanza
I tre riquadri sono le clausole di $(x \lor y) \land (\neg x \lor z) \land (\neg y \lor \neg z)$ , scritte con OR e NOT. La formula è vera solo se lo sono tutte e tre. Gli interruttori sotto servono a scegliere i valori di $x$ , $y$ e $z$ .

Verifica il certificato. Con x = 1, y = 0, z = 1 ogni porta OR ha in uscita un segno di spunta: in x ∨ y è vero x, in ¬ x ∨ z è vero z, in ¬ y ∨ ¬ z è vero ¬ y. La formula vale 1, e per controllarlo è bastato un passaggio per clausola. Se il candidato fallisse, per decidere l'istanza bisognerebbe provarne un altro. — 3. Verifica il certificato
Con $x = 1$ , $y = 0$ , $z = 1$ ogni porta OR ha in uscita un segno di spunta: in $x \lor y$ è vero $x$ , in $\neg x \lor z$ è vero $z$ , in $\neg y \lor \neg z$ è vero $\neg y$ . La formula vale 1, e per controllarlo è bastato un passaggio per clausola. Se il candidato fallisse, per decidere l'istanza bisognerebbe provarne un altro.

Scorri l'immagine o usa Avanti.

Un assegnamento è un certificato: controllare che ogni clausola sia vera richiede tempo polinomiale. Il teorema di Cook-Levin traduce la computazione di una macchina nondeterministica in una formula soddisfacibile esattamente quando esiste un ramo accettante. Con un solo blocco esistenziale, $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_1$ coincide con SAT.

Complemento e collegamenti

Complemento:

SAT si riduce a 3-SAT spezzando le clausole
$\htmlData{term=problem:SAT}{\mathrm{SAT}} = \htmlData{term=problem:QSAT}{\mathrm{QSAT}}_1$
stesso problema, scritto come circuito
SAT → VALIDITY solo se $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}}$
la metà NP di SAT-UNSAT

Teorema di Cook-Levin 3-SAT è NP-completo $\mathrm{2\text{-}SAT} \in \mathrm{P}$ Altri problemi DP-completi Proposizione (oracoli NP-completi equivalenti)Teorema (CIRC SAT e CIRC VALIDITY)Proposizione (FSAT e SAT)Problemi NEXP-completi

Domande e trappole d'esame

F13#3
È vero che $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_1$ non è NP-completo?
NO $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_1 = \htmlData{term=problem:SAT}{\mathrm{SAT}}$ è $\htmlData{term=Σ1}{\Sigma_1^{\mathrm{P}}}$ -completo e $\htmlData{term=Σ1}{\Sigma_1^{\mathrm{P}}} = \htmlData{term=NP}{\mathrm{NP}}$ .
FE23#2
È vero che SAT non appartiene a PP?
NO $\htmlData{term=problem:SAT}{\mathrm{SAT}} \in \htmlData{term=NP}{\mathrm{NP}} \subseteq \htmlData{term=PP}{\mathrm{PP}}$ .
F05#6
È vero che $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_1$ non è L-hard?
NOUn problema NP-completo è hard per ogni classe contenuta in NP, quindi anche per L.
SAT e VALIDITY si riducono l'uno all'altro in tempo polinomiale se e solo se $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}}$ .