Problemi del corso

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

ClasseSolo completiSolo nelle tracce

36 problemi

Problema 27 di 36

co-QSAT_i

Complemento di $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_i$ : la QBF $\exists X_1\, \forall X_2 \ldots \varphi$ è falsa? Equivale a chiedere se $\forall X_1\, \exists X_2 \ldots \neg\varphi$ è vera.

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

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

-completo

Nelle tracce · 19 domande

F02, domanda 7 F03, domanda 1 F03, domanda 5 F04, domanda 1 F06, domanda 2 F07, domanda 2 F08, domanda 5 G16, domanda 6 F12, domanda 2 F12, domanda 5 F13, domanda 1 G20v1, domanda 1 G20v2, domanda 7 LU22, domanda 1 FE23, domanda 3 FE23, domanda 7 SE23, domanda 1 E26, domanda 5 ND, domanda 7

Un esempio, passo dopo passo

1 / 3

Leggi la formula originale. Esempio: ∃x ∀y (x ∧ y). Chiediamo se è falsa. — 1. Leggi la formula originale
Esempio: $\exists x\, \forall y\, (x \land y)$ . Chiediamo se è falsa.

Scorri l'immagine o usa Avanti.

È la domanda opposta a $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_i$ : la formula quantificata è falsa? Non significa semplicemente mettere $\forall$ davanti alla stessa formula.

Per negare una formula si scambiano $\exists$ e $\forall$ e si nega la parte finale: $\neg(\exists x\, \forall y\, \varphi)$ equivale a $\forall x\, \exists y\, \neg\varphi$ . Esempio: $\exists x\, \forall y\, (x \land y)$ è falsa, perché $y = 0$ la rende falsa qualunque $x$ si scelga. Il complemento risponde quindi sì.

$\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_i$ è completo per $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ ; il suo complemento è completo per $\Pi_i^{\htmlData{term=P}{\mathrm{P}}}$ . Con $i = 1$ si ottiene co-SAT, cioè l’insoddisfacibilità.

Complemento e collegamenti

Complemento:

$\htmlData{term=problem:COSAT}{\mathrm{co\text{-}SAT}} = \mathrm{co\text{-}QSAT}_1$

Teorema 17.10 ( $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_i$ è $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ -completo)

Domande e trappole d'esame

G20v1#1
Assumiamo $\htmlData{term=Σ3}{\Sigma_3^{\mathrm{P}}} = \htmlData{term=Π3}{\Pi_3^{\mathrm{P}}}$ . $\mathrm{co\text{-}QSAT}_3$ è $\htmlData{term=Σ3}{\Sigma_3^{\mathrm{P}}}$ -completo?
SÌÈ $\htmlData{term=Π3}{\Pi_3^{\mathrm{P}}}$ -completo e con l'ipotesi $\htmlData{term=Π3}{\Pi_3^{\mathrm{P}}} = \htmlData{term=Σ3}{\Sigma_3^{\mathrm{P}}}$ .
G20v2#7
$\mathrm{co\text{-}QSAT}_3$ è P-hard?
SÌ $\htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=Π3}{\Pi_3^{\mathrm{P}}}$ .
F08#5
$\mathrm{co\text{-}QSAT}_3 \in \htmlData{term=Π3}{\Pi_3^{\mathrm{P}}}$ ?
SÌÈ $\htmlData{term=Π3}{\Pi_3^{\mathrm{P}}}$ -completo.
G16#6
QSAT è riducibile a $\mathrm{co\text{-}QSAT}_3$ ?
altro: solo se $\htmlData{term=PSPACE}{\mathrm{PSPACE}} = \htmlData{term=Π3}{\Pi_3^{\mathrm{P}}}$ Si porterebbe tutto PSPACE dentro $\htmlData{term=Π3}{\Pi_3^{\mathrm{P}}}$ .
FE23#3
$\mathrm{co\text{-}QSAT}_2$ è riducibile a QSAT?
SÌ $\htmlData{term=Π2}{\Pi_2^{\mathrm{P}}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}}$ e QSAT è PSPACE-completo.
F02#7
Supponete che $\mathrm{co\text{-}QSAT}_2$ non sia PH-hard. $\htmlData{term=PSPACE}{\mathrm{PSPACE}} = \htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}$ ?
NOSe $\htmlData{term=PSPACE}{\mathrm{PSPACE}} = \htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}$ , $\htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}$ e il $\htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}$ -completo $\mathrm{co\text{-}QSAT}_2$ sarebbe PH-hard.

Problemi del corso

1. Leggi la formula originale

2. Cerca il valore universale che la smentisce

3. Leggi il complemento