Problemi del corso

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

ClasseSolo completiSolo nelle tracce

36 problemi

Problema 20 di 36

VALIDITY

Data una formula booleana: è vera per ogni assegnamento delle variabili (è una tautologia)?

coNPcoNP-completo

Nelle tracce · 3 domande

F14, domanda 2 G20v2, domanda 3 LU22, domanda 1

Un esempio, passo dopo passo

1 / 3

Leggi la formula. Considera x ∨ ¬x e chiedi se vale per ogni valore di x. — 1. Leggi la formula
Considera $x \lor \neg x$ e chiedi se vale per ogni valore di $x$ .

Scorri l'immagine o usa Avanti.

Un assegnamento che rende falsa la formula certifica una risposta no. La formula $\varphi$ è valida esattamente quando $\neg\varphi$ è insoddisfacibile. Per provare la validità, trovare un solo assegnamento che la rende vera non è sufficiente.

Complemento e collegamenti

Il complemento (esiste un assegnamento che rende falsa

\varphi

) è SAT applicato a

\neg\varphi

: NP-completo.

$\varphi$ valida se e solo se $\neg\varphi$ è insoddisfacibile
SAT → VALIDITY solo se $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}}$

VALIDITY è coNP-completo Teorema (CIRC SAT e CIRC VALIDITY)

Domande e trappole d'esame

G20v2#3
VALIDITY è P-hard?
SÌÈ coNP-completo e $\htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=coNP}{\mathrm{coNP}}$ : è hard per ogni classe contenuta in coNP.
LU22#1
VALIDITY è riducibile a $\mathrm{co\text{-}QSAT}_4$ ?
SÌ $\htmlData{term=coNP}{\mathrm{coNP}} = \htmlData{term=Π1}{\Pi_1^{\mathrm{P}}} \subseteq \htmlData{term=Π4}{\Pi_4^{\mathrm{P}}}$ e $\mathrm{co\text{-}QSAT}_4$ è $\htmlData{term=Π4}{\Pi_4^{\mathrm{P}}}$ -completo.
F14#2
Supponiamo VALIDITY riducibile a TSP(D). È vero che EXACT TSP non è $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ -completo?
NOL'ipotesi dà $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}}$ , quindi $\htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=DP}{\mathrm{DP}} = \htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ , e il DP-completo EXACT TSP diventa $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ -completo.

Problemi del corso

1. Leggi la formula

2. Esamina entrambi i casi

3. Concludi per tutti i valori