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), 20 (crittografia e function problems), 21–22 (NEXP, riepilogo). Slide di P. A. Bonatti delle Lezioni 1–6 e 9, le sole disponibili: il resto si cita dalla dispensa. Le tracce d'esame danno solo le domande: le risposte si motivano con dispensa e slide.

DispensaSlideFuori 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.
esterno $\htmlData{term=R}{\mathrm{R}} = \htmlData{term=RE}{\mathrm{RE}} \cap \htmlData{term=coRE}{\mathrm{coRE}}$ , il teorema di completezza di Gödel e il teorema di Church-Turing per la validità del primo ordine, il prefisso $\exists\ldots\exists\forall\ldots\forall$ del frammento di Schönfinkel-Bernays e la tecnica che spezza le clausole lunghe nella riduzione da SAT a 3-SAT: sono spiegazioni aggiunte, perché la dispensa dà solo i risultati (cap. 1.5, 12, 13.6 e 22).
✱ fuori dalle fonti NL-completezza di REACHABILITY e 2-SAT, P-completezza di CIRCUIT VALUE, HORNSAT e LINEAR PROGRAMMING, 2-COL in L, il nome AKS: vengono dal libro di riferimento o dalla letteratura, non dalla dispensa né dalle slide.
✱ fuori dalle fonti $\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, non è né nella dispensa né nelle slide.
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: la prima segue dalla dispensa (cap. 1.5, 7, 10 e 11), la seconda dalla validità del primo ordine (cap. 22) e da $\htmlData{term=R}{\mathrm{R}} = \htmlData{term=RE}{\mathrm{RE}} \cap \htmlData{term=coRE}{\mathrm{coRE}}$ . Il ragionamento è nelle schede delle classi R e RE.

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 e slide (Lezioni 1–6 e 9).

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.
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}}$ ).