Fonti e verifiche

I riferimenti del corso e le integrazioni, raccolti qui per consultazione.

Fonti del corso

Dispensa Computational Complexity (M. Mignogna, 2025): cap. 1 (R, RE), 2.6 (L), 5–11 (classi, gerarchie, Savitch), 12–13 (NP-completezza), 14 (coNP), 15 (DP), 16 (oracoli), 17 (PH), 19 (giochi), 21–22 (NEXP, riepilogo). Slide di P. A. Bonatti, Lezioni 1–9. Appunti delle Lezioni 3–11 su Notion e pagine delle tracce risolte.

DispensaSlideAppuntiFuori dalle fonti sono le etichette usate nelle schede dei problemi.

Ogni affermazione è stata controllata su queste fonti. Quando un'affermazione non c'è, è separata e marcata con ✱ o con l'etichetta esterno.

Aggiunte esterne e conseguenze ricavate

esterno Il significato della D di DP ("differenza") viene dal libro di Papadimitriou, non da dispensa o slide.
esterno Il promemoria « $\Sigma = \text{somma} = \text{OR} = \exists$ , $\Pi = \text{prodotto} = \text{AND} = \forall$ » e l'origine della notazione dalla gerarchia aritmetica (scheda Piani di PH): dispensa e slide non spiegano le lettere. Che $\exists$ si valuti come OR e $\forall$ come AND invece è nelle slide (algoritmo Truth).
esterno Il nome Immerman–Szelepcsényi per $\htmlData{term=NL}{\mathrm{NL}} = \mathrm{coNL}$ : le slide della Lez. 4 dicono solo che per lo spazio nondeterministico la chiusura per complemento si dimostra.
✱ solo appunti NL-completezza di REACHABILITY e 2-SAT, P-completezza di CIRCUIT VALUE, HORNSAT e LINEAR PROGRAMMING, 2-COL in L, il nome AKS: sono negli appunti o nella letteratura, non in dispensa o nelle slide disponibili.
✱ solo appunti $\htmlData{term=NP}{\mathrm{NP}} \subsetneq \htmlData{term=NEXP}{\mathrm{NEXP}}$ : dispensa (cap. 8) e slide danno la gerarchia di tempo nondeterministico solo tra polinomi, $\mathrm{NTIME}(n^c) \subsetneq \mathrm{NTIME}(n^d)$ . La separazione $\htmlData{term=NP}{\mathrm{NP}} \subsetneq \htmlData{term=NEXP}{\mathrm{NEXP}}$ , usata nelle risposte NO, viene dagli appunti (Lez. 5 §7, dal Papadimitriou).
ricavata $\htmlData{term=NEXP}{\mathrm{NEXP}} \subsetneq \htmlData{term=R}{\mathrm{R}}$ e $\htmlData{term=RE}{\mathrm{RE}} \neq \htmlData{term=coRE}{\mathrm{coRE}}$ non sono scritte così nelle fonti: seguono da risultati del corso (Lez. 10 §4 e §7), con il ragionamento mostrato nella scheda.

Precisazioni sui materiali del corso

Barre di complemento perse. Nel riepilogo della dispensa (cap. 22) e nel cap. 17 "HAMILTON PATH is coNP-complete", "TSP(D) is coNP-complete", " $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_i$ is $\Pi_i^{\htmlData{term=P}{\mathrm{P}}}$ -complete" e "STRATEGIC COMPANIES is $\htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}$ -complete" hanno una barra sopra il nome, cioè parlano del complemento. Sono giusti; la barra sparisce solo se si copia il testo dal PDF.

Verifica della tabella dei problemi

Ogni riga della tabella di partenza della mappa dei problemi, controllata su dispensa, slide delle Lezioni 1–9 e pagine delle tracce risolte.

Riga della tabella	Esito	Cosa dicono le fonti
REACHABILITY: NL-completo, in $\mathrm{SPACE}(\log^2 n)$ (Savitch)	◐ in parte	In NL: slide Lezione 3. In $\mathrm{SPACE}(\log^2 n)$ : slide Lezione 5 e dispensa cap. 7. La NL-completezza non è nelle fonti (viene dal libro di riferimento).
2-SAT: NL-completo, quindi in P; $\htmlData{term=NL}{\mathrm{NL}} = \mathrm{coNL}$ ; 2-SAT non NP-completo, 3-SAT sì	◐ in parte	In P: dispensa cap. 12. $\htmlData{term=NL}{\mathrm{NL}} = \mathrm{coNL}$ : dispensa cap. 6 e slide Lezione 4 dicono che le classi di spazio nondeterministico sono chiuse per complemento. 3-SAT NP-completo: cap. 12. La NL-completezza non è nelle fonti. "2-SAT non è NP-completo" non è dimostrato: lo sarebbe se $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=NL}{\mathrm{NL}}$ .
2-COL: in P, anzi in L; 3-COL NP-completo	◐ in parte	In P e 3-COL NP-completo: dispensa cap. 13. "In L" non è nelle fonti (risultato della letteratura).
MAX FLOW: P-completo; anche LINEAR PROGRAMMING è P-completo	◐ in parte	MAX FLOW P-completo: dispensa cap. 22. LINEAR PROGRAMMING: la dispensa dice solo che sta in P (cap. 13); la P-completezza non è nelle fonti.
PRIMES: in P (algoritmo AKS)	◐ in parte	$\htmlData{term=problem:PRIMES}{\mathrm{PRIMES}} \in \htmlData{term=P}{\mathrm{P}}$ : dispensa cap. 22. Il nome AKS non compare nelle fonti.
SAT, 3-SAT, CLIQUE, 3-COL, TSP(D), HAMILTON PATH, INDEPENDENT SET, NODE COVER: NP-completi; $\htmlData{term=problem:SAT}{\mathrm{SAT}} = \htmlData{term=problem:QSAT}{\mathrm{QSAT}}_1$	✔ confermata	Tutti NP-completi nella dispensa (cap. 12, 13, 22). $\htmlData{term=problem:SAT}{\mathrm{SAT}} = \htmlData{term=problem:QSAT}{\mathrm{QSAT}}_1$ segue dalla definizione di $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_i$ (slide Lezione 9) ed è la risposta del correttore in F13#3.
VALIDITY, co-SAT, $\mathrm{co\text{-}QSAT}_1$ , complementi di HAMILTON PATH e TSP(D): coNP-completi	✔ confermata	Dispensa cap. 14 e cap. 22 (nomi con la barra). Nota: co-SAT e $\mathrm{co\text{-}QSAT}_1$ sono lo stesso problema.
SAT-UNSAT, EXACT TSP: DP-completi; $\htmlData{term=DP}{\mathrm{DP}} = \{A \cap B : A \in \htmlData{term=NP}{\mathrm{NP}},\ B \in \htmlData{term=coNP}{\mathrm{coNP}}\}$	✔ confermata	Definizione di DP, SAT-UNSAT e EXACT TSP DP-completi: slide Lezione 9; SAT-UNSAT anche nella dispensa cap. 22.
$\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_i$ : $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ -completo, il complemento $\Pi_i^{\htmlData{term=P}{\mathrm{P}}}$ -completo	✔ confermata	Slide Lezione 9 e dispensa cap. 22.
QSAT, GEOGRAPHY: PSPACE-completi, quindi hard anche per le classi inferiori	✔ confermata	Slide Lezione 9, dispensa cap. 19 e 22. Un problema completo per PSPACE è hard per ogni classe contenuta in PSPACE.
SCHÖNFINKEL-BERNAYS SAT, SUCCINCT CIRCUIT SAT: NEXP-completi	✔ confermata	Dispensa cap. 13.6 e cap. 22; appunti Lezione 10 §6.
Validità del primo ordine: $\htmlData{term=RE}{\mathrm{RE}} \setminus \htmlData{term=R}{\mathrm{R}}$	✔ confermata	Dispensa cap. 22 (anche la soddisfacibilità: $\htmlData{term=coRE}{\mathrm{coRE}} \setminus \htmlData{term=R}{\mathrm{R}}$ ); appunti Lezione 10 §7.