Problemi del corso

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

ClasseSolo completiSolo nelle tracce

36 problemi

Problema 26 di 36

QSAT_i

Formula booleana quantificata $\exists X_1\, \forall X_2\, \exists X_3 \ldots \varphi$ con $i$ blocchi di quantificatori alternati, il primo esistenziale: è vera?

\Sigma_i^{\mathrm{P}}

\Sigma_i^{\htmlData{term=P}{\mathrm{P}}}

-completo

Nelle tracce · 14 domande

F04, domanda 1 F05, domanda 6 F07, domanda 7 F08, domanda 3 G16, domanda 4 F13, domanda 1 F13, domanda 3 F14, domanda 6 L18, domanda 5 G20v4, domanda 1 G20v5, domanda 2 GE23, domanda 1 GE23, domanda 5 SE23, domanda 6

Un esempio, passo dopo passo

1 / 3

Leggi il prefisso. La formula è ∃ x ∀ y (x ∨ y), con i = 2 blocchi. L'albero la segue dall'alto: la radice ∃ x si divide nei rami x₀ e x₁, cioè x = 0 e x = 1, e sotto ciascuno un nodo ∀ y apre i due valori di y. Le foglie grigie sono i valori di x ∨ y, ancora da calcolare. — 1. Leggi il prefisso
La formula è $\exists x\, \forall y\, (x \lor y)$ , con $i = 2$ blocchi. L'albero la segue dall'alto: la radice $\exists x$ si divide nei rami $x_0$ e $x_1$ , cioè $x = 0$ e $x = 1$ , e sotto ciascuno un nodo $\forall y$ apre i due valori di $y$ . Le foglie grigie sono i valori di $x \lor y$ , ancora da calcolare.

Scorri l'immagine o usa Avanti.

$\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_1$ , cioè $\exists x\, \varphi$ , è SAT: basta un assegnamento. $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_2$ , cioè $\exists x\, \forall y\, \varphi$ , richiede una scelta di $x$ che funzioni per entrambi i valori di $y$ . Per esempio $\exists x\, \forall y\, (x \lor y)$ è vera scegliendo $x = 1$ , mentre con $x = 0$ fallisce per $y = 0$ .

Al secondo livello la formula è $\exists X\, \forall Y\, \varphi(X, Y)$ . La macchina sceglie i valori di $X$ , li sostituisce in $\varphi$ e deve poi stabilire se $\varphi$ è vera per ogni possibile $Y$ .

Per farlo chiede all'oracolo SAT la domanda opposta: esiste un $Y$ che rende falsa $\varphi$ con questi valori di $X$ , cioè $\neg\varphi(X, Y)$ è soddisfacibile? Se l'oracolo risponde no, non ci sono controesempi e la scelta di $X$ funziona; se risponde sì, quella scelta viene scartata.

Con $i$ blocchi, dopo aver fissato il primo ne restano $i - 1$ . Negando la formula residua i quantificatori si scambiano e il primo diventa $\exists$ , quindi la domanda appartiene a $\Sigma_{i-1}^{\htmlData{term=P}{\mathrm{P}}}$ : l'oracolo la decide e la macchina ne inverte la risposta. Per $i = 1$ non restano blocchi e basta valutare direttamente la formula.

Complemento e collegamenti

Complemento:

$\htmlData{term=problem:SAT}{\mathrm{SAT}} = \htmlData{term=problem:QSAT}{\mathrm{QSAT}}_1$
con i fissato si sta in $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ ; con alternanze libere si arriva a PSPACE
STRATEGIC COMPANIES e $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_2$ sono entrambi $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ -completi
CIRC SAT e $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_2$ sono entrambi $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ -completi

Teorema 17.10 ( $\mathrm{QSAT}_i$ è $\Sigma_i^{\mathrm{P}}$ -completo)

Domande e trappole d'esame

G16#4
È vero che $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_3$ non è coNP-hard?
NO $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_3$ è $\htmlData{term=Σ3}{\Sigma_3^{\mathrm{P}}}$ -completo e $\htmlData{term=coNP}{\mathrm{coNP}} = \htmlData{term=Π1}{\Pi_1^{\mathrm{P}}} \subseteq \htmlData{term=Σ3}{\Sigma_3^{\mathrm{P}}}$ .
GE23#1
$\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_2$ è $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ -hard?
SÌÈ $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ -completo.
F14#6
È vero che $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_1$ non appartiene a $\htmlData{term=Σ4}{\Sigma_4^{\mathrm{P}}}$ ?
NO $\htmlData{term=Σ1}{\Sigma_1^{\mathrm{P}}} \subseteq \htmlData{term=Σ4}{\Sigma_4^{\mathrm{P}}}$ .
G20v4#1
Supponiamo $\htmlData{term=L}{\mathrm{L}} \subset \htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ . $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_2$ è L-completo?
NOStarebbe in L, quindi $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}} \subseteq \htmlData{term=L}{\mathrm{L}}$ , contro l'ipotesi. È L-hard, ma non sta in L.
La barra sopra il nome di un problema ne indica il complemento: per $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_i$ equivale a chiedere se la formula quantificata è falsa.

Problemi del corso

1. Leggi il prefisso

2. Fissa la scelta esistenziale

3. Combina i rami universali