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. Esempio ∃x ∀y ∃z [z ↔ (x ⊕ y)]. L’ultima scelta può dipendere da y. — 1. Leggi l’alternanza
Esempio $\exists x\, \forall y\, \exists z\, [z \leftrightarrow (x \oplus y)]$ . L’ultima scelta può dipendere da $y$ .

Scorri l'immagine o usa Avanti.

SAT cerca un assegnamento; QSAT valuta scelte e condizioni universali nell’ordine indicato. $\exists$ significa che basta una scelta; $\forall$ significa che devono funzionare entrambe, 0 e 1.

In $\exists x\, \forall y\, \exists z\, (z \leftrightarrow (x \oplus y))$ , scegli prima $x$ . Poi, per ciascun valore di $y$ , puoi scegliere uno $z$ diverso: con $x = 0$ , scegli $z = 0$ quando $y = 0$ e $z = 1$ quando $y = 1$ . La formula è vera. Una scelta esistenziale può dipendere dai valori universali che la precedono.

Si esplora l’albero: 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; $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_i$ , invece, 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, $\htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}$ -completo solo se $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\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 $\htmlData{term=PSPACE}{\mathrm{PSPACE}} = \htmlData{term=Π2}{\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