Le risorse del calcolo

Classi di complessità

Separazioni dimostrate Questioni aperte

inclusione dimostrata, non si sa se stretta

inclusione stretta dimostrata

separazione dimostrata tra classi lontane

non si sa nemmeno se una contiene l'altra

\htmlData{term=NL}{\mathrm{NL}}

Spazio logaritmico nondeterministico

= \mathrm{coNL}

chiusa per complemento: sì:

\htmlData{term=NL}{\mathrm{NL}} = \mathrm{coNL}

Confronta con…

Come L, ma la macchina può fare scelte nondeterministiche e risponde sì se almeno un run accetta. In memoria tiene solo dove si trova e indovina dove andare. È la classe tipica della raggiungibilità in un grafo.

Dove sta: inclusioni e questioni aperte

È contenuta in

\subseteq

\subseteq

NP ∩ coNP

\subseteq

\subseteq

coNP

\subseteq

\subseteq

Δ₂^P

\subseteq

Σ₂^P

\subseteq

Π₂^P

\subseteq

Σ_i^P

\subseteq

Π_i^P

\subseteq

\subsetneq

PSPACE

\subsetneq

EXP

\subsetneq

NEXP

\subsetneq

\subsetneq

\subsetneq

coRE

Contiene

\supseteq

Rapporto non noto

nessuna

$\subsetneq$ in rosso: inclusione stretta dimostrata (anche quando segue dal fatto che l'inclusione opposta è esclusa). $\subseteq$ senza colore: dimostrata, non si sa se stretta. ? : non si sa nemmeno se una contenga l'altra. $\neq$ : diverse, ma nessuna contiene l'altra.

Problemi completi

REACHABILITY e 2-SAT sono NL-completi (appunti Lez. 8 §3; Lez. 10 §8). ✱ solo appunti La dispensa dà solo $\htmlData{term=problem:REACH}{\mathrm{REACHABILITY}} \in \htmlData{term=NL}{\mathrm{NL}}$ e, per Savitch, $\in \mathrm{SPACE}(\log^2 n)$ .

Trappola. 2-SAT sta in P (dispensa cap. 12); la NL-completezza viene dagli appunti ✱, non da dispensa o slide. Con riduzioni in spazio logaritmico 2-SAT sarebbe P-completo solo se

\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NL}{\mathrm{NL}}

, che è aperto: all'esame «2-SAT è P-completo?» ha risposta «altro: solo se

\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NL}{\mathrm{NL}}

».

$\htmlData{term=NL}{\mathrm{NL}} = \mathrm{coNL}$ . Le slide della Lez. 4 dicono che per lo spazio nondeterministico la chiusura per complemento si dimostra; per il tempo nondeterministico (NP contro coNP) è aperta.

Aggiunta esterna. Il risultato si chiama Teorema di Immerman–Szelepcsényi (Papadimitriou, Teorema 7.6): il nome non è nelle slide.

Problemi: REACHABILITY · 2-SAT

Teoremi su NL

Proposizione (MdT con input e output) · REACHABILITY in spazio logaritmico nondeterministico · Gerarchie nondeterministiche · Teorema 7.4 (a) · Teorema 7.4 (c) · Corollario (catena $\mathrm{L} \subseteq \mathrm{NL} \subseteq \mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE}$ ) · Teorema di Savitch (Teorema 7.5) · Corollario di Savitch (spazio nondeterministico) · Chiusura delle classi rispetto alle riduzioni · 2-SAT è P-completo se e solo se $\mathrm{P} = \mathrm{NL}$

Dalle tracce d'esame

È vero che 2-SAT non appartiene a DP? (F01)

\htmlData{term=problem:SAT2}{2\text{-}\mathrm{SAT}} \in \htmlData{term=NL}{\mathrm{NL}} \subseteq \htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=NP}{\mathrm{NP}} \subseteq \htmlData{term=DP}{\mathrm{DP}}

È vero che 2-SAT non può essere deciso da una MdT nondeterministica in spazio polinomiale? (MA23)

\htmlData{term=problem:SAT2}{2\text{-}\mathrm{SAT}} \in \htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}} = \mathrm{NPSPACE}

GEOGRAPHY è NL-hard? (MA23)

SÌ

PSPACE-completo e

\htmlData{term=NL}{\mathrm{NL}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}}

Supponiamo SCHÖNFINKEL-BERNAYS SAT

\in \htmlData{term=BPP}{\mathrm{BPP}}

. È vero che GEOGRAPHY non è riducibile a 2-SAT? (GE23)

SÌ

L'ipotesi non serve: GEOGRAPHY è PSPACE-completo e

\htmlData{term=problem:SAT2}{2\text{-}\mathrm{SAT}} \in \htmlData{term=NL}{\mathrm{NL}}

; con riduzioni in spazio logaritmico avremmo

\htmlData{term=PSPACE}{\mathrm{PSPACE}} \subseteq \htmlData{term=NL}{\mathrm{NL}}

, contro

\htmlData{term=NL}{\mathrm{NL}} \subsetneq \htmlData{term=PSPACE}{\mathrm{PSPACE}}

Fonti: dispensa cap. 5 e 11; slide Lez. 4–5; appunti Lez. 3, 5 §10, 8 §3