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. Formula: (x ∨ y) ∧ (¬x ∨ z) ∧ (¬y ∨ ¬z). Tutte le clausole devono essere vere. — 1. Leggi l’istanza
Formula: $(x \lor y) \land (\neg x \lor z) \land (\neg y \lor \neg z)$ . Tutte le clausole devono essere vere.

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 $\htmlData{term=problem:SAT2}{\mathrm{2\text{-}SAT}} \in \htmlData{term=P}{\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}}$ .

Problemi del corso

1. Leggi l’istanza

2. Scegli un assegnamento

3. Verifica il certificato