Problemi del corso

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

ClasseSolo completiSolo nelle tracce

36 problemi

Problema 31 di 36

QSAT

Formula booleana quantificata con un numero qualsiasi di alternanze di quantificatori: è vera?

PSPACEPSPACE-completo

Nelle tracce · 6 domande

F05, domanda 7 G16, domanda 6 F13, domanda 6 L18, domanda 4 FE23, domanda 3 SE23, domanda 3

Un esempio, passo dopo passo

1 / 3

Leggi l'alternanza. La formula è ∃ x ∀ y ∃ z [z leftrightarrow (x ⊕ y)]. L'albero ha un livello per quantificatore, ognuno con il suo colore: ∃ x in cima, poi ∀ y, poi ∃ z; le etichette dei rami, come x₀ o y₁, indicano x = 0 e y = 1. Poiché z si sceglie sotto y, la scelta può dipendere da y. — 1. Leggi l'alternanza
La formula è $\exists x\, \forall y\, \exists z\, [z \leftrightarrow (x \oplus y)]$ . L'albero ha un livello per quantificatore, ognuno con il suo colore: $\exists x$ in cima, poi $\forall y$ , poi $\exists z$ ; le etichette dei rami, come $x_0$ o $y_1$ , indicano $x = 0$ e $y = 1$ . Poiché $z$ si sceglie sotto $y$ , la scelta può dipendere da $y$ .

Scorri l'immagine o usa Avanti.

SAT cerca un assegnamento; QSAT valuta scelte e condizioni universali nell'ordine indicato. Con $\exists$ basta una scelta, con $\forall$ devono funzionare entrambi i valori, 0 e 1.

In $\exists x\, \forall y\, \exists z\, (z \leftrightarrow (x \oplus y))$ si sceglie prima $x$ ; poi, per ciascun valore di $y$ , si può scegliere uno $z$ diverso. Con $x = 0$ basta $z = 0$ quando $y = 0$ e $z = 1$ quando $y = 1$ , quindi la formula è vera: una scelta esistenziale può dipendere dai valori universali che la precedono.

Per decidere si esplora l'albero delle scelte: per $\exists$ basta un ramo vero, per $\forall$ devono essere veri entrambi. Una visita in profondità riusa lo spazio tra i rami e usa spazio polinomiale. Qui il numero di blocchi può crescere con l'input, mentre $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_i$ fissa $i$ in anticipo.

Complemento e collegamenti

Nessun complemento associato.

con i fissato si sta in $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ ; con alternanze libere si arriva a PSPACE
entrambi PSPACE-completi: una partita è un'alternanza $\exists\forall$

QSAT è PSPACE-completo Complemento di HAMILTON PATH: coNP-completo, $\Pi_2^{\mathrm{P}}$ -completo solo se $\mathrm{NP} = \mathrm{coNP}$

Domande e trappole d'esame

F07#7
$\htmlData{term=problem:QSAT}{\mathrm{QSAT}} \in \htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}$ ?
altro: solo se $\mathrm{PSPACE} = \Pi_2^{\mathrm{P}}$ PH collasserebbe al livello 2.
L18#4
$\htmlData{term=problem:QSAT}{\mathrm{QSAT}} \in \htmlData{term=EXP}{\mathrm{EXP}}$ ?
SÌ $\htmlData{term=PSPACE}{\mathrm{PSPACE}} \subseteq \htmlData{term=EXP}{\mathrm{EXP}}$ .
F13#6
QSAT è 2-EXP-completo?
NO $\htmlData{term=problem:QSAT}{\mathrm{QSAT}} \in \htmlData{term=EXP}{\mathrm{EXP}} \subsetneq 2\text{-}\mathrm{EXP}$ .
F05#7
QSAT è P-hard?
SÌ $\htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}}$ .
L18#1
Se $\htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=EXP}{\mathrm{EXP}}$ , PH collassa a un livello finito?
SÌ $\htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=PSPACE}{\mathrm{PSPACE}}$ , e $\htmlData{term=problem:QSAT}{\mathrm{QSAT}} \in \htmlData{term=PH}{\mathrm{PH}}$ starebbe in qualche $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ : allora $\htmlData{term=PH}{\mathrm{PH}} = \Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ .

Problemi del corso

1. Leggi l'alternanza

2. Segui una strategia

3. Valuta dal basso