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^{\htmlData{term=P}{\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. Esempio i = 2: ∃x ∀y (x ∨ y). Prima scegli x, poi considera ogni y. — 1. Leggi il prefisso
Esempio $i = 2$ : $\exists x\, \forall y\, (x \lor y)$ . Prima scegli $x$ , poi considera ogni $y$ .

Scorri l'immagine o usa Avanti.

$\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_1$ : $\exists x\, \varphi$ è SAT: basta un assegnamento. $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_2$ : $\exists x\, \forall y\, \varphi$ richiede una scelta di $x$ che funzioni per entrambi i valori di $y$ . Esempio: $\exists x\, \forall y\, (x \lor y)$ è vera scegliendo $x = 1$ ; scegliendo $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$ e li sostituisce in $\varphi$ . Deve poi stabilire se $\varphi$ è vera per ogni possibile $Y$ .

All’oracolo SAT chiede la domanda opposta: «Esiste un $Y$ che rende falsa $\varphi$ con questi valori di $X$ ?», cioè se $\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$ . Si nega 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 decide questa domanda; la macchina ne inverte la risposta. Per $i = 1$ , senza blocchi residui, 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 ( $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_i$ è $\Sigma_i^{\htmlData{term=P}{\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