Teoremi del corso

Dove: dispensa cap. 3, p. 18; slide Lez. 3

teorema

Teorema (da nondeterministico a deterministico)

chiesto in 7 domandedimostrato nel corso

Se $L$ è deciso da una MdT nondeterministica $N$ in tempo $f(n)$ , allora è deciso da una MdT deterministica a 3 nastri in tempo $O(c^{f(n)})$ , con $c \gt 1$ costante che dipende da $N$ . In breve: $\mathrm{NTIME}(f(n)) \subseteq \bigcup_{c \gt 1} \mathrm{TIME}(c^{f(n)})$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

La macchina deterministica prova una dopo l'altra tutte le sequenze di scelte, che sono al più $d^{f(n)}$ ( $d$ è il grado di nondeterminismo).

All'esame

Dà $\htmlData{term=NP}{\mathrm{NP}} \subseteq \htmlData{term=EXP}{\mathrm{EXP}}$ : togliere il nondeterminismo dal tempo, per quanto si sa oggi, costa un esponenziale.

Da scrivere all'esame

Per il teorema da nondeterministico a deterministico $\mathrm{NTIME}(f(n)) \subseteq \bigcup_{c \gt 1} \mathrm{TIME}(c^{f(n)})$ : simulare il nondeterminismo costa un esponenziale, quindi per esempio $\htmlData{term=NP}{\mathrm{NP}} \subseteq \htmlData{term=EXP}{\mathrm{EXP}}$ .

Dimostrazione illustrata

1 / 4

Numera le scelte. In ogni situazione la macchina nondeterministica N ha al più d mosse possibili, numerate da 1 a d come gli archi che escono dalla radice. Un ramo di t passi è quindi una sequenza (c₁, …, c_t) di numeri fra 1 e d, dove cᵢ dice quale mossa fare al passo i. Le sequenze che scelgono una mossa inesistente si scartano. — 1. Numera le scelte
In ogni situazione la macchina nondeterministica $N$ ha al più $d$ mosse possibili, numerate da 1 a $d$ come gli archi che escono dalla radice. Un ramo di $t$ passi è quindi una sequenza $(c_1, \ldots, c_t)$ di numeri fra 1 e $d$ , dove $c_i$ dice quale mossa fare al passo $i$ . Le sequenze che scelgono una mossa inesistente si scartano.

Conta i rami. Con f(n) livelli le sequenze sono d + d² + cdots + d^(f(n)) = O(d^(f(n))), perché l'ultimo termine vale almeno quanto tutti gli altri insieme. Ognuna costa O(f(n)) passi fra generazione e simulazione, e f(n) · d^(f(n)) ≤ (2d)^(f(n)): il tempo è O(c^(f(n))) con c = 2d > d, una costante che dipende da N e non dall'input. — 4. Conta i rami
Con $f(n)$ livelli le sequenze sono $d + d^2 + \cdots + d^{f(n)} = O(d^{f(n)})$ , perché l'ultimo termine vale almeno quanto tutti gli altri insieme. Ognuna costa $O(f(n))$ passi fra generazione e simulazione, e $f(n) \cdot d^{f(n)} \le (2d)^{f(n)}$ : il tempo è $O(c^{f(n)})$ con $c = 2d \gt d$ , una costante che dipende da $N$ e non dall'input.

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F05 n. 4 · G20v1 n. 5 · G20v2 n. 5 · G20v4 n. 5 · G20v5 n. 5 · LU24 n. 3 · SP n. 3

Classi

NP EXP

Dove: dispensa cap. 3, p. 20; slide Lez. 3

proposizione

REACHABILITY in spazio logaritmico nondeterministico

per l'oraledimostrato nel corso

REACHABILITY si decide con una MdT nondeterministica in spazio $O(\log n)$ : $\htmlData{term=problem:REACH}{\mathrm{REACHABILITY}} \in \htmlData{term=NL}{\mathrm{NL}}$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

La macchina ricorda solo il nodo corrente e il prossimo, scelto nondeterministicamente: due numeri tra 1 e $n$ , cioè $O(\log n)$ celle.

All'esame

Esempio tipico di problema in NL; è anche il punto di partenza del Teorema di Savitch.

Da scrivere all'esame

SÌ: $\htmlData{term=problem:REACH}{\mathrm{REACHABILITY}} \in \htmlData{term=NL}{\mathrm{NL}}$ , perché una MdT nondeterministica indovina il cammino ricordando solo il nodo corrente e il successivo, cioè $O(\log n)$ celle di lavoro.

Dimostrazione illustrata

1 / 4

Ricorda solo dove sei. Il grafo, con la sorgente s in verde e la destinazione t in rosso, sta sul nastro di input, in sola lettura, che non si conta nello spazio. Sul nastro di lavoro la macchina tiene solo il nodo corrente, all'inizio s. Segnare i nodi già visitati, come fa una visita del grafo, costerebbe un bit per nodo, troppo per lo spazio logaritmico. — 1. Ricorda solo dove sei
Il grafo, con la sorgente $s$ in verde e la destinazione $t$ in rosso, sta sul nastro di input, in sola lettura, che non si conta nello spazio. Sul nastro di lavoro la macchina tiene solo il nodo corrente, all'inizio $s$ . Segnare i nodi già visitati, come fa una visita del grafo, costerebbe un bit per nodo, troppo per lo spazio logaritmico.

Scegli e verifica il prossimo nodo. Dal nodo corrente u la macchina sceglie in modo nondeterministico un nodo v, la freccia tratteggiata, e legge sul nastro di input se l'arco (u, v) c'è. Se manca, quel ramo rifiuta; se c'è e v = t, accetta; altrimenti v prende il posto di u e si ripete. Un ramo che rifiuta ha solo scelto male: per accettare basta un ramo che segue un cammino vero. — 2. Scegli e verifica il prossimo nodo
Dal nodo corrente $u$ la macchina sceglie in modo nondeterministico un nodo $v$ , la freccia tratteggiata, e legge sul nastro di input se l'arco $(u, v)$ c'è. Se manca, quel ramo rifiuta; se c'è e $v = t$ , accetta; altrimenti $v$ prende il posto di $u$ e si ripete. Un ramo che rifiuta ha solo scelto male: per accettare basta un ramo che segue un cammino vero.

Conta i bit. Il nastro di lavoro contiene tre numeri scritti in binario: il nodo corrente u, il prossimo nodo (questa v è un nome di nodo, non il numero dei nodi) e il contatore i. Ognuno occupa O(log v) bit, in tutto O(log v): con un milione di nodi, circa 60 bit. Basta che un ramo trovi il cammino, quindi REACHABILITY ∈ NL. — 4. Conta i bit
Il nastro di lavoro contiene tre numeri scritti in binario: il nodo corrente $u$ , il prossimo nodo (questa $v$ è un nome di nodo, non il numero dei nodi) e il contatore $i$ . Ognuno occupa $O(\log v)$ bit, in tutto $O(\log v)$ : con un milione di nodi, circa 60 bit. Basta che un ramo trovi il cammino, quindi $\htmlData{term=problem:REACH}{\mathrm{REACHABILITY}} \in \htmlData{term=NL}{\mathrm{NL}}$ .

Scorri l'immagine o usa Avanti.

Dimostrazione

Classi

NL

Problemi

REACHABILITY

Dove: slide Lez. 3. Presentato nelle slide (algoritmo a 3 nastri); la dispensa non lo enuncia come risultato a sé.

Capitolo 4 · Funzioni di complessità proprie

teorema

Teorema delle soluzioni precise

per l'oraledimostrato nel corso

Se $M$ decide $L$ in tempo o spazio $f(n)$ , con $f$ propria, allora esiste una MdT precisa $M'$ che decide $L$ in tempo o spazio $O(f(n))$ . Precisa vuol dire che, su ogni input $x$ , ogni computazione si ferma dopo un numero di passi che dipende solo da $|x|$ e i nastri di lavoro hanno una lunghezza che dipende solo da $|x|$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

Prima si calcola il "metro" lungo $f(|x|)$ con la macchina $M_f$ , poi lo si usa come sveglia (tempo) o come limite di memoria (spazio).

Da scrivere all'esame

Per il teorema delle soluzioni precise, con $f$ propria si può supporre che tempo o spazio della MdT dipendano solo da $|x|$ , restando nel budget $O(f(n))$ .

Dimostrazione illustrata

1 / 4

Costruisci un metro. Il teorema vuole una macchina precisa, la cui durata e il cui spazio dipendono solo dalla lunghezza n dell'input. Siccome f è propria, una macchina M_f scrive esattamente f(n) quasi-blank, i # del disegno, in tempo O(n + f(n)), e anche i suoi passi dipendono solo da n. Questo nastro fa da metro. — 1. Costruisci un metro
Il teorema vuole una macchina precisa, la cui durata e il cui spazio dipendono solo dalla lunghezza $n$ dell'input. Siccome $f$ è propria, una macchina $M_f$ scrive esattamente $f(n)$ quasi-blank, i $\#$ del disegno, in tempo $O(n + f(n))$ , e anche i suoi passi dipendono solo da $n$ . Questo nastro fa da metro.

Usalo come recinto. Per lo spazio, M' copia il metro su ogni nastro di lavoro e simula M scrivendo sopra i quasi-blank #, che tratta come blank; l'input resta in alto, sul suo nastro in sola lettura. Le celle verdi sono quelle che M usa: al più f(n) per nastro, quindi non esce dal recinto. Le altre restano # e occupano spazio come le prime, così ogni nastro di lavoro è lungo esattamente f(n), tutta la parentesi. — 3. Usalo come recinto
Per lo spazio, $M'$ copia il metro su ogni nastro di lavoro e simula $M$ scrivendo sopra i quasi-blank $\#$ , che tratta come blank; l'input resta in alto, sul suo nastro in sola lettura. Le celle verdi sono quelle che $M$ usa: al più $f(n)$ per nastro, quindi non esce dal recinto. Le altre restano $\#$ e occupano spazio come le prime, così ogni nastro di lavoro è lungo esattamente $f(n)$ , tutta la parentesi.

Conserva il risultato. La risposta y è quella di M, mentre durata e spazio dipendono solo da n. Per il tempo, M_f costa O(n + f(n)) e la simulazione f(n) passi, in tutto O(f(n)) perché un budget di tempo è almeno n; per lo spazio, O(f(n)) per M_f più le k copie del metro. Se M' si fermasse insieme a M, la durata tornerebbe a dipendere dall'input. — 4. Conserva il risultato
La risposta $y$ è quella di $M$ , mentre durata e spazio dipendono solo da $n$ . Per il tempo, $M_f$ costa $O(n + f(n))$ e la simulazione $f(n)$ passi, in tutto $O(f(n))$ perché un budget di tempo è almeno $n$ ; per lo spazio, $O(f(n))$ per $M_f$ più le $k$ copie del metro. Se $M'$ si fermasse insieme a $M$ , la durata tornerebbe a dipendere dall'input.

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove: dispensa cap. 4, p. 21; slide Lez. 4

teorema

Teorema (terminazione delle MdT space-bounded)

per l'oraledimostrato nel corso

Se $M$ decide $L$ in spazio $f(n)$ , con $f$ propria, allora esiste $M'$ che decide $L$ in spazio $O(f(n))$ e tale che ogni sua computazione termina.

Idea, frase per l'esame e dimostrazione +

Intuizione

Le configurazioni possibili sono al più $|K| \cdot |\Sigma|^{f(n)} \cdot (f(n)+1)$ : se la macchina fa più passi di così è in un ciclo, e la si può fermare in "no".

All'esame

È l'idea dietro $\mathrm{SPACE}(f(n)) \subseteq \mathrm{TIME}(k^{f(n)})$ e quindi $\htmlData{term=PSPACE}{\mathrm{PSPACE}} \subseteq \htmlData{term=EXP}{\mathrm{EXP}}$ .

Da scrivere all'esame

Per il teorema di terminazione, una MdT con budget di spazio $f(n)$ ( $f$ propria) si rende sempre terminante: ha al più $|K| \cdot |\Sigma|^{f(n)} \cdot (f(n)+1)$ configurazioni, oltre le quali è in un ciclo.

Dimostrazione illustrata

1 / 4

Conta le configurazioni possibili. Una configurazione è una fotografia completa della macchina: lo stato q, il contenuto a₁ … a_s del nastro di lavoro e le posizioni dei cursori. Con spazio s = f(n) si scrive in O(s) bit; l'ipotesi s ≥ log n serve perché ci stia anche la posizione sul nastro di input, che ha n + 1 valori possibili. Le configurazioni diverse sono quindi al più 2^(O(s)). — 1. Conta le configurazioni possibili
Una configurazione è una fotografia completa della macchina: lo stato $q$ , il contenuto $a_1 \ldots a_s$ del nastro di lavoro e le posizioni dei cursori. Con spazio $s = f(n)$ si scrive in $O(s)$ bit; l'ipotesi $s \ge \log n$ serve perché ci stia anche la posizione sul nastro di input, che ha $n + 1$ valori possibili. Le configurazioni diverse sono quindi al più $2^{O(s)}$ .

Taglia i cicli. In alto, un ramo che accetta entra nel ciclo rosso e torna a una configurazione già vista. Le mosse che fa dopo la seconda occorrenza sono lecite anche dalla prima, perché la configurazione è la stessa: togliendo il giro resta il ramo in basso, più corto, che accetta ancora. Tagliando tutte le ripetizioni si ottiene un ramo che accetta in al più tanti passi quante sono le configurazioni. — 2. Taglia i cicli
In alto, un ramo che accetta entra nel ciclo rosso e torna a una configurazione già vista. Le mosse che fa dopo la seconda occorrenza sono lecite anche dalla prima, perché la configurazione è la stessa: togliendo il giro resta il ramo in basso, più corto, che accetta ancora. Tagliando tutte le ripetizioni si ottiene un ramo che accetta in al più tanti passi quante sono le configurazioni.

Aggiungi un contatore. M' simula un ramo di M e intanto fa scendere un contatore partito da c = 2^(O(s)), il numero delle configurazioni. Se il ramo accetta prima, M' accetta; se il contatore arriva a 0 e il ramo non si è fermato, M' lo chiude in rifiuto. Il linguaggio non cambia, perché se x ∈ L un ramo che accetta entro c passi c'è comunque. — 3. Aggiungi un contatore
$M'$ simula un ramo di $M$ e intanto fa scendere un contatore partito da $c = 2^{O(s)}$ , il numero delle configurazioni. Se il ramo accetta prima, $M'$ accetta; se il contatore arriva a 0 e il ramo non si è fermato, $M'$ lo chiude in rifiuto. Il linguaggio non cambia, perché se $x \in L$ un ramo che accetta entro $c$ passi c'è comunque.

Scorri l'immagine o usa Avanti.

Dimostrazione

Classi

PSPACE EXP

Dove: dispensa cap. 4, p. 22; slide Lez. 4

Capitolo 6 · Classi complementari

proposizione

Proposizione (le classi deterministiche sono chiuse per complemento)

chiesto in 2 domandedimostrato nel corso

Se $C$ è una classe deterministica $\mathrm{TIME}(f(n))$ o $\mathrm{SPACE}(f(n))$ , allora $C = \mathrm{co}C$ ; per esempio $\htmlData{term=P}{\mathrm{P}} = \mathrm{coP}$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

Basta scambiare gli stati "yes" e "no" della macchina deterministica.

All'esame

Serve a dire che $\htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=coNP}{\mathrm{coNP}}$ e che, se $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ , allora anche $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}}$ .

Da scrivere all'esame

SÌ: le classi deterministiche di tempo e spazio sono chiuse per complemento (per esempio $\htmlData{term=P}{\mathrm{P}} = \mathrm{coP}$ ): basta scambiare "yes" e "no" nella MdT deterministica, con lo stesso budget.

Dimostrazione illustrata

1 / 3

Parti da un decisore. M è deterministica e decide L entro il budget di tempo o di spazio: su ogni input x si ferma e risponde sì esattamente quando x ∈ L. Serve che M termini sempre, come dice la scritta in basso: se su qualche input girasse all'infinito, scambiare le uscite non le farebbe accettare quell'input, che pure sta nel complemento. — 1. Parti da un decisore
$M$ è deterministica e decide $L$ entro il budget di tempo o di spazio: su ogni input $x$ si ferma e risponde sì esattamente quando $x \in L$ . Serve che $M$ termini sempre, come dice la scritta in basso: se su qualche input girasse all'infinito, scambiare le uscite non le farebbe accettare quell'input, che pure sta nel complemento.

Conserva le risorse. M' risponde sì esattamente sugli x ∉ L, quindi decide L̄ con lo stesso tempo e lo stesso spazio di M. Per C = TIME(f(n)) o SPACE(f(n)) questo dà C = coC, e quindi anche P = coP. Su una macchina nondeterministica lo scambio non funziona: i rami che rifiutavano accetterebbero anche quando un altro ramo accettava. — 3. Conserva le risorse
$M'$ risponde sì esattamente sugli $x \notin L$ , quindi decide $\overline{L}$ con lo stesso tempo e lo stesso spazio di $M$ . Per $C = \mathrm{TIME}(f(n))$ o $\mathrm{SPACE}(f(n))$ questo dà $C = \mathrm{co}C$ , e quindi anche $\htmlData{term=P}{\mathrm{P}} = \mathrm{coP}$ . Su una macchina nondeterministica lo scambio non funziona: i rami che rifiutavano accetterebbero anche quando un altro ramo accettava.

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F05 n. 2 · F08 n. 3

Classi

P L PSPACE EXP

Dove: dispensa cap. 6, p. 25; slide Lez. 4

Capitolo 7 · Teorema di gerarchia

lemma

Lemma 1 (limite superiore per $H_f$ )

per l'oraledimostrato nel corso

Per $f(n) \ge n$ propria, il linguaggio $H_f = \{M;x : M \text{ accetta } x \text{ in al più } f(|x|) \text{ passi}\}$ sta in $\mathrm{TIME}(f(n)^3)$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

Una macchina universale con una "sveglia" lunga $f(|x|)$ simula $M$ passo per passo, e ogni passo costa $O(f(n)^2)$ .

Da scrivere all'esame

Per il Lemma 1, $H_f \in \mathrm{TIME}(f(n)^3)$ : una macchina universale con una sveglia lunga $f(|x|)$ simula $M$ su $x$ spendendo $O(f(n)^2)$ per ogni passo.

Dimostrazione illustrata

1 / 4

Ricevi programma e input. H_f contiene le coppie M;x in cui M accetta x in al più f(|x|) passi. La macchina universale U riceve tutta la coppia come input: la descrizione ⟨ M ⟩, cioè il programma di M, e la stringa x. Il tempo di U si misura sulla lunghezza n dell'intera coppia, descrizione compresa. — 1. Ricevi programma e input
$H_f$ contiene le coppie $M;x$ in cui $M$ accetta $x$ in al più $f(|x|)$ passi. La macchina universale $U$ riceve tutta la coppia come input: la descrizione $\langle M \rangle$ , cioè il programma di $M$ , e la stringa $x$ . Il tempo di $U$ si misura sulla lunghezza $n$ dell'intera coppia, descrizione compresa.

Prepara il conto alla rovescia. Siccome f è propria, U costruisce con M_f una sveglia di f(|x|) celle, in tempo O(n + f(n)) = O(f(n)) perché f(n) ≥ n. Nel disegno la sveglia conta da f(|x|) a 0: ogni passo simulato consuma una cella. Conta f(|x|) passi perché così è definito H_f; siccome f non decresce e |x| ≤ n, vale f(|x|) ≤ f(n). — 2. Prepara il conto alla rovescia
Siccome $f$ è propria, $U$ costruisce con $M_f$ una sveglia di $f(|x|)$ celle, in tempo $O(n + f(n)) = O(f(n))$ perché $f(n) \ge n$ . Nel disegno la sveglia conta da $f(|x|)$ a 0: ogni passo simulato consuma una cella. Conta $f(|x|)$ passi perché così è definito $H_f$ ; siccome $f$ non decresce e $|x| \le n$ , vale $f(|x|) \le f(n)$ .

Simula entro il budget. U simula M su x un passo alla volta: cerca la transizione nel programma, aggiorna i nastri codificati di M e fa scendere la sveglia (la freccia "passo"). Se M accetta prima che la sveglia arrivi a 0, U accetta; se M rifiuta o la sveglia finisce, rifiuta. Con |x| = 3 e f(n) = n² la sveglia vale 9: un'accettazione al passo 7 conta, una al passo 12 no. — 3. Simula entro il budget
$U$ simula $M$ su $x$ un passo alla volta: cerca la transizione nel programma, aggiorna i nastri codificati di $M$ e fa scendere la sveglia (la freccia "passo"). Se $M$ accetta prima che la sveglia arrivi a 0, $U$ accetta; se $M$ rifiuta o la sveglia finisce, rifiuta. Con $|x| = 3$ e $f(n) = n^2$ la sveglia vale 9: un'accettazione al passo 7 conta, una al passo 12 no.

Calcola il costo universale. A ogni passo U scorre i nastri codificati di M, lunghi O(f(n)), con un numero di passate che dipende da M: un fattore ℓ_M · k_M², con k_M nastri e ℓ_M bit per stato o simbolo. U deve rispettare un solo limite per tutte le M, quindi il fattore si limita con log³ n = O(f(n)) e un passo costa O(f(n)²). Per f(n) passi, O(f(n)³). — 4. Calcola il costo universale
A ogni passo $U$ scorre i nastri codificati di $M$ , lunghi $O(f(n))$ , con un numero di passate che dipende da $M$ : un fattore $\ell_M \cdot k_M^2$ , con $k_M$ nastri e $\ell_M$ bit per stato o simbolo. $U$ deve rispettare un solo limite per tutte le $M$ , quindi il fattore si limita con $\log^3 n = O(f(n))$ e un passo costa $O(f(n)^2)$ . Per $f(n)$ passi, $O(f(n)^3)$ .

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove: dispensa cap. 7, p. 26; slide Lez. 5

lemma

Lemma 2 (limite inferiore per $H_f$ )

per l'oraledimostrato nel corso

$H_f \notin \mathrm{TIME}(f(\lfloor n/2 \rfloor))$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

Diagonalizzazione: se una macchina decidesse $H_f$ così in fretta, la macchina $D_f$ che "fa il contrario" sulla propria descrizione porterebbe a una contraddizione.

Da scrivere all'esame

Per il Lemma 2, $H_f \notin \mathrm{TIME}(f(\lfloor n/2 \rfloor))$ : la macchina diagonale $D_f$ , che fa il contrario sulla propria descrizione, porterebbe a una contraddizione.

Dimostrazione illustrata

1 / 4

Supponi un decisore troppo veloce. Per assurdo, una macchina M_H decide H_f in tempo f(⌊ n/2 ⌋), dove n è la lunghezza della coppia ⟨ M ⟩; x: nel disegno è il riquadro rosso, che su ogni coppia si ferma in sì o in no. La domanda a cui risponde è se M accetta x in al più f(|x|) passi. — 1. Supponi un decisore troppo veloce
Per assurdo, una macchina $M_H$ decide $H_f$ in tempo $f(\lfloor n/2 \rfloor)$ , dove $n$ è la lunghezza della coppia $\langle M \rangle; x$ : nel disegno è il riquadro rosso, che su ogni coppia si ferma in sì o in no. La domanda a cui risponde è se $M$ accetta $x$ in al più $f(|x|)$ passi.

Costruisci la macchina opposta. D riceve la descrizione di una macchina M, esegue M_H sulla coppia ⟨ M ⟩; ⟨ M ⟩ e inverte la risposta: chiede se M accetta la propria descrizione entro f(|⟨ M ⟩|) passi e fa l'opposto. Se la descrizione è lunga n, la coppia è lunga 2n+1 e M_H impiega f(⌊ (2n+1)/2 ⌋) = f(n) passi: il ⌊ n/2 ⌋ del budget compensa il raddoppio. — 2. Costruisci la macchina opposta
$D$ riceve la descrizione di una macchina $M$ , esegue $M_H$ sulla coppia $\langle M \rangle; \langle M \rangle$ e inverte la risposta: chiede se $M$ accetta la propria descrizione entro $f(|\langle M \rangle|)$ passi e fa l'opposto. Se la descrizione è lunga $n$ , la coppia è lunga $2n+1$ e $M_H$ impiega $f(\lfloor (2n+1)/2 \rfloor) = f(n)$ passi: il $\lfloor n/2 \rfloor$ del budget compensa il raddoppio.

Dai a D la propria descrizione. Ora l'input di D è la sua stessa descrizione ⟨ D ⟩, lunga n, e M_H deve dire se D accetta ⟨ D ⟩ entro f(n) passi. D si ferma sempre entro f(n) passi, a parte il tempo lineare per scrivere la coppia, quindi per D "accetta entro f(n) passi" e "accetta" sono la stessa cosa. — 3. Dai a $D$ la propria descrizione
Ora l'input di $D$ è la sua stessa descrizione $\langle D \rangle$ , lunga $n$ , e $M_H$ deve dire se $D$ accetta $\langle D \rangle$ entro $f(n)$ passi. $D$ si ferma sempre entro $f(n)$ passi, a parte il tempo lineare per scrivere la coppia, quindi per $D$ "accetta entro $f(n)$ passi" e "accetta" sono la stessa cosa.

Ottieni la contraddizione. Se M_H prevede "sì", D inverte e rifiuta, quindi non accetta affatto. Se prevede "no", D inverte e accetta, entro f(n) passi. In tutti e due i casi la previsione è sbagliata, quindi M_H non esiste e H_f ∉ TIME(f(⌊ n/2 ⌋)). Con un decisore lento quanto la macchina universale, D uscirebbe dal budget e il secondo caso non darebbe contraddizione. — 4. Ottieni la contraddizione
Se $M_H$ prevede "sì", $D$ inverte e rifiuta, quindi non accetta affatto. Se prevede "no", $D$ inverte e accetta, entro $f(n)$ passi. In tutti e due i casi la previsione è sbagliata, quindi $M_H$ non esiste e $H_f \notin \mathrm{TIME}(f(\lfloor n/2 \rfloor))$ . Con un decisore lento quanto la macchina universale, $D$ uscirebbe dal budget e il secondo caso non darebbe contraddizione.

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove: dispensa cap. 7, p. 27; slide Lez. 5

teorema

Teorema di gerarchia per il tempo (Teorema 7.1)

★ chiesto in 30 domandedimostrato nel corso

Se $f(n) \ge n$ è una funzione propria, allora $\mathrm{TIME}(f(n)) \subsetneq \mathrm{TIME}(f(2n+1)^3)$ . È stato dimostrato anche il risultato più forte $\mathrm{TIME}(f(n)) \subsetneq \mathrm{TIME}(f(n) \cdot \log^2 f(n))$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

Con abbastanza tempo in più si risolvono problemi nuovi: con $g(n) = f(2n+1)$ , $H_g$ sta nella classe grande (Lemma 1) ma non in quella piccola (Lemma 2).

All'esame

Serve a separare classi di tempo, per esempio a dimostrare $\htmlData{term=P}{\mathrm{P}} \subsetneq \htmlData{term=EXP}{\mathrm{EXP}}$ .

Da scrivere all'esame

Per il teorema di gerarchia per il tempo, se $f(n) \ge n$ è propria allora $\mathrm{TIME}(f(n)) \subsetneq \mathrm{TIME}(f(2n+1)^3)$ : con abbastanza tempo in più si risolvono problemi nuovi.

Dimostrazione illustrata

1 / 4

Confronta due budget. Sia g(n) = f(2n+1). Siccome f non decresce e f(2n+1) ≥ 2n+1 ≥ 1, vale f(n) ≤ f(2n+1) ≤ g(n)³: una macchina che sta nel budget piccolo sta anche in quello grande, e l'ovale di TIME(f(n)) sta dentro quello di TIME(g(n)³). Resta da trovare un linguaggio dentro l'ovale grande e fuori da quello piccolo. — 1. Confronta due budget
Sia $g(n) = f(2n+1)$ . Siccome $f$ non decresce e $f(2n+1) \ge 2n+1 \ge 1$ , vale $f(n) \le f(2n+1) \le g(n)^3$ : una macchina che sta nel budget piccolo sta anche in quello grande, e l'ovale di $\mathrm{TIME}(f(n))$ sta dentro quello di $\mathrm{TIME}(g(n)^3)$ . Resta da trovare un linguaggio dentro l'ovale grande e fuori da quello piccolo.

Scegli il linguaggio testimone. Il linguaggio è H_g: le coppie M;x in cui M accetta x entro g(|x|) passi. Anche g è propria (si calcola 2n+1 e poi si usa M_f) e g(n) ≥ n, quindi il Lemma 1 vale per g: una macchina universale con la sveglia decide H_g in tempo O(g(n)³) = O(f(2n+1)³), come nel riquadro. — 2. Scegli il linguaggio testimone
Il linguaggio è $H_g$ : le coppie $M;x$ in cui $M$ accetta $x$ entro $g(|x|)$ passi. Anche $g$ è propria (si calcola $2n+1$ e poi si usa $M_f$ ) e $g(n) \ge n$ , quindi il Lemma 1 vale per $g$ : una macchina universale con la sveglia decide $H_g$ in tempo $O(g(n)^3) = O(f(2n+1)^3)$ , come nel riquadro.

Escludi la classe piccola. Supponi H_g ∈ TIME(f(n)). Per n pari 2⌊ n/2 ⌋ + 1 = n+1, per n dispari vale n, quindi g(⌊ n/2 ⌋) = f(2⌊ n/2 ⌋ + 1) ≥ f(n) e H_g starebbe anche in TIME(g(⌊ n/2 ⌋)). Il lemma diagonale, cioè il Lemma 2 applicato a g, lo esclude: è la contraddizione del disegno. — 3. Escludi la classe piccola
Supponi $H_g \in \mathrm{TIME}(f(n))$ . Per $n$ pari $2\lfloor n/2 \rfloor + 1 = n+1$ , per $n$ dispari vale $n$ , quindi $g(\lfloor n/2 \rfloor) = f(2\lfloor n/2 \rfloor + 1) \ge f(n)$ e $H_g$ starebbe anche in $\mathrm{TIME}(g(\lfloor n/2 \rfloor))$ . Il lemma diagonale, cioè il Lemma 2 applicato a $g$ , lo esclude: è la contraddizione del disegno.

Concludi la separazione. H_g è il punto dentro TIME(g(n)³) e fuori da TIME(f(n)), quindi TIME(f(n)) ⊊ TIME(f(2n+1)³). Con f(n) = n si ottiene TIME(n) ⊊ TIME((2n+1)³), cioè, a meno di costanti, TIME(n) ⊊ TIME(n³). Un gradino così non basta a separare TIME(n) da TIME(n²). — 4. Concludi la separazione
$H_g$ è il punto dentro $\mathrm{TIME}(g(n)^3)$ e fuori da $\mathrm{TIME}(f(n))$ , quindi $\mathrm{TIME}(f(n)) \subsetneq \mathrm{TIME}(f(2n+1)^3)$ . Con $f(n) = n$ si ottiene $\mathrm{TIME}(n) \subsetneq \mathrm{TIME}((2n+1)^3)$ , cioè, a meno di costanti, $\mathrm{TIME}(n) \subsetneq \mathrm{TIME}(n^3)$ . Un gradino così non basta a separare $\mathrm{TIME}(n)$ da $\mathrm{TIME}(n^2)$ .

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F01 n. 2 · F01 n. 4 · F02 n. 1 · F02 n. 5 · F03 n. 4 · F04 n. 1 · F04 n. 6 · F05 n. 1 · F06 n. 1 · F06 n. 4 · F06 n. 5 · F07 n. 1 · F08 n. 1 · G16 n. 1 · F12 n. 7 · F13 n. 6 · F14 n. 1 · G17 n. 2 · L18 n. 2 · G20v1 n. 2 · G20v1 n. 7 · G20v2 n. 2 · G20v4 n. 2 · LU22 n. 4 · GE23 n. 4 · GE23 n. 6 · E26 n. 4 · E26 n. 7 · ND n. 3 · ND n. 5

Classi

P EXP

Dove: dispensa cap. 7, p. 28; slide Lez. 5. La versione con $\log^2 f(n)$ è citata senza prova (Problema 7.4.8 del Papadimitriou).

teorema

Teorema (separazione di P ed EXP)

★ chiesto in 12 domandedimostrato nel corso

$\htmlData{term=P}{\mathrm{P}} \subsetneq \htmlData{term=EXP}{\mathrm{EXP}}$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

$\htmlData{term=P}{\mathrm{P}} \subseteq \mathrm{TIME}(2^n)$ e, per la gerarchia, $\mathrm{TIME}(2^n) \subsetneq \mathrm{TIME}((2^{2n+1})^3) \subseteq \mathrm{TIME}(2^{n^2}) \subseteq \htmlData{term=EXP}{\mathrm{EXP}}$ .

All'esame

Serve a rispondere NO a " $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=EXP}{\mathrm{EXP}}$ ?" e a escludere riduzioni da problemi completi per EXP (o classi più grandi, come NEXP) verso problemi in P.

Da scrivere all'esame

$\htmlData{term=P}{\mathrm{P}} \subsetneq \htmlData{term=EXP}{\mathrm{EXP}}$ : per il teorema di gerarchia $\mathrm{TIME}(2^n) \subsetneq \mathrm{TIME}(2^{6n+3}) \subseteq \htmlData{term=EXP}{\mathrm{EXP}}$ , e $\htmlData{term=P}{\mathrm{P}} \subseteq \mathrm{TIME}(2^n)$ , quindi $\htmlData{term=P}{\mathrm{P}} \subsetneq \htmlData{term=EXP}{\mathrm{EXP}}$ .

Dimostrazione illustrata

1 / 3

Raccogli tutti i polinomi. Nel grafico la curva verde 2ⁿ parte sotto la linea nᵏ, la incrocia in n₀ (il tratteggio) e da lì resta sempre sopra. Per gli n minori di n₀ la differenza è una costante, che lo speedup lineare assorbe. Quindi ogni TIME(nᵏ) sta in TIME(2ⁿ), e con loro l'unione P. — 1. Raccogli tutti i polinomi
Nel grafico la curva verde $2^n$ parte sotto la linea $n^k$ , la incrocia in $n_0$ (il tratteggio) e da lì resta sempre sopra. Per gli $n$ minori di $n_0$ la differenza è una costante, che lo speedup lineare assorbe. Quindi ogni $\mathrm{TIME}(n^k)$ sta in $\mathrm{TIME}(2^n)$ , e con loro l'unione $\htmlData{term=P}{\mathrm{P}}$ .

Applica la gerarchia. Il riquadro è il teorema di gerarchia del tempo applicato a f(n) = 2ⁿ, e ne esce un linguaggio H con due proprietà. In alto, H si decide in tempo 2^(cn) con c costante (il conto preciso dà 2⁶ⁿ⁺³ ≤ 2⁹ⁿ), e la freccia verde scende a H ∈ EXP perché 2^(cn) ≤ 2^(n^2) per n ≥ c. In basso, in rosa, H ∉ TIME(2ⁿ). — 2. Applica la gerarchia
Il riquadro è il teorema di gerarchia del tempo applicato a $f(n) = 2^n$ , e ne esce un linguaggio $H$ con due proprietà. In alto, $H$ si decide in tempo $2^{cn}$ con $c$ costante (il conto preciso dà $2^{6n+3} \le 2^{9n}$ ), e la freccia verde scende a $H \in \htmlData{term=EXP}{\mathrm{EXP}}$ perché $2^{cn} \le 2^{n^2}$ per $n \ge c$ . In basso, in rosa, $H \notin \mathrm{TIME}(2^n)$ .

Escludi tutta P. Gli ovali annidati riassumono la catena: P dentro TIME(2ⁿ), che sta dentro EXP. Il punto verde H è in EXP ma fuori dall'ovale grigio di TIME(2ⁿ), quindi anche fuori da P, che è contenuta lì. Un linguaggio di EXP che non sta in P basta per concludere P ⊊ EXP. — 3. Escludi tutta P
Gli ovali annidati riassumono la catena: $\htmlData{term=P}{\mathrm{P}}$ dentro $\mathrm{TIME}(2^n)$ , che sta dentro $\htmlData{term=EXP}{\mathrm{EXP}}$ . Il punto verde $H$ è in $\htmlData{term=EXP}{\mathrm{EXP}}$ ma fuori dall'ovale grigio di $\mathrm{TIME}(2^n)$ , quindi anche fuori da $\htmlData{term=P}{\mathrm{P}}$ , che è contenuta lì. Un linguaggio di $\htmlData{term=EXP}{\mathrm{EXP}}$ che non sta in $\htmlData{term=P}{\mathrm{P}}$ basta per concludere $\htmlData{term=P}{\mathrm{P}} \subsetneq \htmlData{term=EXP}{\mathrm{EXP}}$ .

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F01 n. 2 · F01 n. 4 · F02 n. 1 · F02 n. 5 · F04 n. 1 · F06 n. 5 · G16 n. 1 · G17 n. 2 · G20v1 n. 2 · G20v1 n. 7 · GE23 n. 4 · E26 n. 7

Classi

P EXP

Dove: dispensa cap. 7, p. 28; slide Lez. 5

Capitolo 10 · Spazio dato il tempo

teorema

Spazio dato il tempo

★ chiesto in 25 domandedimostrato nel corso

$\mathrm{SPACE}(f(n)) \subseteq \mathrm{TIME}(k^{f(n)})$ per una costante $k$ ; in particolare $\htmlData{term=PSPACE}{\mathrm{PSPACE}} \subseteq \htmlData{term=EXP}{\mathrm{EXP}}$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

Una macchina con spazio $f(n)$ ha un numero di configurazioni esponenziale in $f(n)$ : se fa più passi di così è in un ciclo.

All'esame

Dà $\htmlData{term=PSPACE}{\mathrm{PSPACE}} \subseteq \htmlData{term=EXP}{\mathrm{EXP}}$ (non si sa se l'inclusione è stretta).

Da scrivere all'esame

$\mathrm{SPACE}(f(n)) \subseteq \mathrm{TIME}(k^{f(n)})$ , perché una macchina con budget di spazio $f(n)$ ha al più $k^{f(n)}$ configurazioni; quindi $\htmlData{term=PSPACE}{\mathrm{PSPACE}} \subseteq \htmlData{term=EXP}{\mathrm{EXP}}$ .

Dimostrazione illustrata

1 / 4

Descrivi una configurazione. Fra parentesi c'è una configurazione: lo stato q e un nastro di lavoro con la sua testina (il triangolo); i puntini stanno per il resto, cioè gli altri nastri e la posizione sull'input. Con f(n) ≥ log n anche quella posizione, circa log n bit, rientra in O(f(n)). Stringhe di O(f(n)) bit sono al più c^(f(n)), con c che dipende solo dalla macchina. — 1. Descrivi una configurazione
Fra parentesi c'è una configurazione: lo stato $q$ e un nastro di lavoro con la sua testina (il triangolo); i puntini stanno per il resto, cioè gli altri nastri e la posizione sull'input. Con $f(n) \ge \log n$ anche quella posizione, circa $\log n$ bit, rientra in $O(f(n))$ . Stringhe di $O(f(n))$ bit sono al più $c^{f(n)}$ , con $c$ che dipende solo dalla macchina.

Segui il cammino deterministico. La macchina è deterministica, quindi ogni configurazione ne determina una sola successiva e la computazione è la catena C₀ → C₁ → C₂ → C₃. Se da C₃ si tornasse a C₁, la freccia rossa, da lì la macchina rifarebbe le stesse mosse, ritornerebbe a C₁ e girerebbe per sempre senza fermarsi. — 2. Segui il cammino deterministico
La macchina è deterministica, quindi ogni configurazione ne determina una sola successiva e la computazione è la catena $C_0 \to C_1 \to C_2 \to C_3$ . Se da $C_3$ si tornasse a $C_1$ , la freccia rossa, da lì la macchina rifarebbe le stesse mosse, ritornerebbe a $C_1$ e girerebbe per sempre senza fermarsi.

Sostituisci un polinomio. Con f(n) = nᵏ il limite diventa c^(n^k) = 2^(n^k log c). Per n ≥ log c l'esponente è al più nᵏ⁺¹, quindi ogni SPACE(nᵏ) sta in TIME(2^nᵏ⁺¹) ⊆ EXP, e così la loro unione: PSPACE ⊆ EXP. Non si sa se l'inclusione è stretta. — 4. Sostituisci un polinomio
Con $f(n) = n^k$ il limite diventa $c^{n^k} = 2^{n^k \log c}$ . Per $n \ge \log c$ l'esponente è al più $n^{k+1}$ , quindi ogni $\mathrm{SPACE}(n^k)$ sta in $\mathrm{TIME}(2^{n^{k+1}}) \subseteq \htmlData{term=EXP}{\mathrm{EXP}}$ , e così la loro unione: $\htmlData{term=PSPACE}{\mathrm{PSPACE}} \subseteq \htmlData{term=EXP}{\mathrm{EXP}}$ . Non si sa se l'inclusione è stretta.

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F01 n. 1 · F02 n. 5 · F03 n. 4 · F04 n. 6 · F05 n. 1 · F06 n. 1 · F06 n. 4 · F07 n. 1 · F08 n. 1 · F12 n. 7 · F13 n. 6 · L18 n. 1 · L18 n. 4 · G20v2 n. 2 · G20v4 n. 2 · LU22 n. 4 · FE23 n. 4 · MA23 n. 6 · SE23 n. 3 · SE23 n. 5 · LU24 n. 1 · LU24 n. 6 · E26 n. 4 · E26 n. 6 · ND n. 5

Classi

PSPACE EXP

Dove: dispensa cap. 10, p. 29; slide Lez. 5

Capitolo 11 · Deterministico vs nondeterministico (Savitch)

proposizione

Teorema 7.4 (a)

per l'oraledimostrato nel corso

$\mathrm{TIME}(f(n)) \subseteq \mathrm{NTIME}(f(n))$ e $\mathrm{SPACE}(f(n)) \subseteq \mathrm{NSPACE}(f(n))$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

Le MdT deterministiche sono casi particolari di quelle nondeterministiche.

All'esame

Inclusioni di base come $\htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=NP}{\mathrm{NP}}$ , $\htmlData{term=L}{\mathrm{L}} \subseteq \htmlData{term=NL}{\mathrm{NL}}$ e $\htmlData{term=PSPACE}{\mathrm{PSPACE}} \subseteq \mathrm{NPSPACE}$ .

Da scrivere all'esame

SÌ, per il Teorema 7.4 (a): una MdT deterministica è un caso particolare di nondeterministica, quindi $\mathrm{TIME}(f(n)) \subseteq \mathrm{NTIME}(f(n))$ e $\mathrm{SPACE}(f(n)) \subseteq \mathrm{NSPACE}(f(n))$ .

Dimostrazione illustrata

1 / 3

Prendi la macchina deterministica. M legge il nastro (la testina è sotto la b) e rispetta il budget f(n) che entra dall'alto, di tempo o di spazio. La sua funzione di transizione δ associa a ogni coppia di stato q e simbolo letto σ una sola azione (q', tau, D): nuovo stato, simbolo da scrivere e direzione della testina. — 1. Prendi la macchina deterministica
$M$ legge il nastro (la testina è sotto la $b$ ) e rispetta il budget $f(n)$ che entra dall'alto, di tempo o di spazio. La sua funzione di transizione $\delta$ associa a ogni coppia di stato $q$ e simbolo letto $\sigma$ una sola azione $(q', \tau, D)$ : nuovo stato, simbolo da scrivere e direzione della testina.

Mantieni il budget. N ha un solo ramo, identico alla computazione di M (la doppia freccia): accetta se e solo se M accetta, fa gli stessi passi e usa le stesse celle. Il budget f(n) vale quindi per entrambe, e se ne ricavano le due inclusioni nei riquadri. Dicono solo che il nondeterminismo non perde problemi; se ne guadagni, con budget polinomiale, è la domanda P contro NP, ancora aperta. — 3. Mantieni il budget
$N$ ha un solo ramo, identico alla computazione di $M$ (la doppia freccia): accetta se e solo se $M$ accetta, fa gli stessi passi e usa le stesse celle. Il budget $f(n)$ vale quindi per entrambe, e se ne ricavano le due inclusioni nei riquadri. Dicono solo che il nondeterminismo non perde problemi; se ne guadagni, con budget polinomiale, è la domanda $\htmlData{term=P}{\mathrm{P}}$ contro $\htmlData{term=NP}{\mathrm{NP}}$ , ancora aperta.

Scorri l'immagine o usa Avanti.

Dimostrazione

Classi

P NP L NL

Dove: slide Lez. 5; dispensa cap. 11, p. 32 (usato nel corollario PSPACE = NPSPACE)

teorema

Teorema 7.4 (b)

chiesto in 3 domandedimostrato nel corso

$\mathrm{NTIME}(f(n)) \subseteq \mathrm{SPACE}(f(n))$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

Si provano le sequenze di scelte una alla volta riusando lo stesso spazio: ogni computazione è lunga al più $f(n)$ .

All'esame

Dà $\htmlData{term=NP}{\mathrm{NP}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}}$ .

Da scrivere all'esame

SÌ, per il Teorema 7.4 (b) $\mathrm{NTIME}(f(n)) \subseteq \mathrm{SPACE}(f(n))$ (si provano i rami uno alla volta riusando lo spazio); per esempio $\htmlData{term=NP}{\mathrm{NP}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}}$ .

Dimostrazione illustrata

1 / 3

Esplora l'albero delle scelte. Ogni nodo dell'albero è una configurazione di N e ogni figlio una scelta possibile; un ramo dalla radice in giù è una computazione. La barra a destra dice che nessun ramo supera f(n) passi. I rami però possono essere fino a d^(f(n)), con d il numero massimo di scelte per passo, e tenere in memoria l'albero intero costerebbe troppo. — 1. Esplora l'albero delle scelte
Ogni nodo dell'albero è una configurazione di $N$ e ogni figlio una scelta possibile; un ramo dalla radice in giù è una computazione. La barra a destra dice che nessun ramo supera $f(n)$ passi. I rami però possono essere fino a $d^{f(n)}$ , con $d$ il numero massimo di scelte per passo, e tenere in memoria l'albero intero costerebbe troppo.

Conta lo spazio. Lo spazio di M ha due parti. Le scelte del ramo sono al più f(n) cifre fra 1 e d, con d costante. La configurazione simulata viene da al più f(n) passi, quindi occupa al più f(n)+1 celle per nastro. In tutto O(f(n)), e M accetta appena un ramo accetta: NTIME(f(n)) ⊆ SPACE(f(n)). — 3. Conta lo spazio
Lo spazio di $M$ ha due parti. Le scelte del ramo sono al più $f(n)$ cifre fra 1 e $d$ , con $d$ costante. La configurazione simulata viene da al più $f(n)$ passi, quindi occupa al più $f(n)+1$ celle per nastro. In tutto $O(f(n))$ , e $M$ accetta appena un ramo accetta: $\mathrm{NTIME}(f(n)) \subseteq \mathrm{SPACE}(f(n))$ .

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F04 n. 5 · G20v1 n. 6 · SE23 n. 7

Classi

NP PSPACE

Dove: dispensa cap. 11, p. 30; slide Lez. 5

teorema

Teorema 7.4 (c)

chiesto in 5 domandedimostrato nel corso

$\mathrm{NSPACE}(f(n)) \subseteq \mathrm{TIME}(k^{\log n + f(n)})$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

Si risolve REACHABILITY sul grafo delle configurazioni, che ha un numero di nodi esponenziale in $\log n + f(n)$ .

All'esame

Con $f(n) = \log n$ dà $\htmlData{term=NL}{\mathrm{NL}} \subseteq \htmlData{term=P}{\mathrm{P}}$ .

Da scrivere all'esame

SÌ, per il Teorema 7.4 (c) $\mathrm{NSPACE}(f(n)) \subseteq \mathrm{TIME}(k^{\log n + f(n)})$ (REACHABILITY sul grafo delle configurazioni); con $f(n) = \log n$ dà $\htmlData{term=NL}{\mathrm{NL}} \subseteq \htmlData{term=P}{\mathrm{P}}$ .

Dimostrazione illustrata

1 / 4

Trasforma configurazioni in nodi. Un nodo v = (q, i, w) è una configurazione di N: lo stato q, la posizione i della testina sull'input e il contenuto w dei nastri di lavoro, con le loro testine. L'input non serve, perché è sempre x. Scrivere i costa circa log n bit e w costa O(f(n)): da qui gli O(log n + f(n)) bit della graffa. — 1. Trasforma configurazioni in nodi
Un nodo $v = (q, i, w)$ è una configurazione di $N$ : lo stato $q$ , la posizione $i$ della testina sull'input e il contenuto $w$ dei nastri di lavoro, con le loro testine. L'input non serve, perché è sempre $x$ . Scrivere $i$ costa circa $\log n$ bit e $w$ costa $O(f(n))$ : da qui gli $O(\log n + f(n))$ bit della graffa.

Calcola gli archi quando servono. C'è un arco da (q, i, w) a (q', j, w') quando una mossa di N porta dalla prima configurazione alla seconda, e le scelte nondeterministiche diventano nodi con più archi uscenti. Il grafo non si scrive in anticipo: quando la visita chiede se una coppia è un arco, la macchina simula una mossa a partire dalla prima configurazione. — 2. Calcola gli archi quando servono
C'è un arco da $(q, i, w)$ a $(q', j, w')$ quando una mossa di $N$ porta dalla prima configurazione alla seconda, e le scelte nondeterministiche diventano nodi con più archi uscenti. Il grafo non si scrive in anticipo: quando la visita chiede se una coppia è un arco, la macchina simula una mossa a partire dalla prima configurazione.

Cerca una configurazione accettante. La visita parte dalla configurazione iniziale, start, e cerca un cammino fino a una configurazione accettante, acc; in alto le frecce verdi ne segnano l'inizio e la fine. Il cammino esiste se e solo se qualche ramo di N accetta x. Così decidere x ∈ L diventa un problema di REACHABILITY, che una visita deterministica risolve in tempo polinomiale nel numero di nodi. — 3. Cerca una configurazione accettante
La visita parte dalla configurazione iniziale, start, e cerca un cammino fino a una configurazione accettante, acc; in alto le frecce verdi ne segnano l'inizio e la fine. Il cammino esiste se e solo se qualche ramo di $N$ accetta $x$ . Così decidere $x \in L$ diventa un problema di REACHABILITY, che una visita deterministica risolve in tempo polinomiale nel numero di nodi.

Conta i nodi. Le configurazioni sono al più 2^(O(log n + f(n))), e la visita costa un polinomio nel loro numero. Con f(n) = O(log n) l'esponente diventa O(log n) e 2^(O(log n)) = n^(O(1)): con tre simboli, per esempio, un nastro lungo log₂ n ha 3^(log₂ n) = n^(log₂ 3) contenuti, circa n^1,58. I nodi sono polinomiali, e NL ⊆ P. — 4. Conta i nodi
Le configurazioni sono al più $2^{O(\log n + f(n))}$ , e la visita costa un polinomio nel loro numero. Con $f(n) = O(\log n)$ l'esponente diventa $O(\log n)$ e $2^{O(\log n)} = n^{O(1)}$ : con tre simboli, per esempio, un nastro lungo $\log_2 n$ ha $3^{\log_2 n} = n^{\log_2 3}$ contenuti, circa $n^{1{,}58}$ . I nodi sono polinomiali, e $\htmlData{term=NL}{\mathrm{NL}} \subseteq \htmlData{term=P}{\mathrm{P}}$ .

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F02 n. 6 · F06 n. 7 · F12 n. 1 · G20v3 n. 7 · SP n. 5

Classi

NL P

Dove: dispensa cap. 11, p. 30; slide Lez. 5. La dispensa omette la prova; le slide la svolgono.

teorema

Teorema di Savitch (Teorema 7.5)

chiesto in 7 domandedimostrato nel corso

$\htmlData{term=problem:REACH}{\mathrm{REACHABILITY}} \in \mathrm{SPACE}(\log^2 n)$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

Un cammino lungo al più $2^i$ da $x$ a $y$ ha un punto di mezzo $z$ : si prova ogni $z$ ricorsivamente riusando lo spazio; la ricorsione è profonda $\log n$ e ogni livello usa $O(\log n)$ celle.

All'esame

È la base dei corollari $\mathrm{NSPACE}(f(n)) \subseteq \mathrm{SPACE}(f(n)^2)$ e $\htmlData{term=PSPACE}{\mathrm{PSPACE}} = \mathrm{NPSPACE}$ .

Da scrivere all'esame

Per il teorema di Savitch $\htmlData{term=problem:REACH}{\mathrm{REACHABILITY}} \in \mathrm{SPACE}(\log^2 n)$ : si cerca ricorsivamente il punto di mezzo del cammino, con ricorsione profonda $\log n$ e $O(\log n)$ bit per livello.

Dimostrazione illustrata

1 / 6

Dimezza il cammino. La curva lilla in alto chiede se da x si arriva a y con al più 2ⁱ archi. Le curve verdi passano per un nodo di mezzo z, da x a z e da z a y, con al più 2ⁱ⁻¹ archi ciascuna. Si usa 2ⁱ perché si dimezza senza arrotondamenti, e i conta i dimezzamenti che restano. La macchina non sa quale nodo sia z, quindi li prova tutti, uno dopo l'altro. — 1. Dimezza il cammino
La curva lilla in alto chiede se da $x$ si arriva a $y$ con al più $2^i$ archi. Le curve verdi passano per un nodo di mezzo $z$ , da $x$ a $z$ e da $z$ a $y$ , con al più $2^{i-1}$ archi ciascuna. Si usa $2^i$ perché si dimezza senza arrotondamenti, e $i$ conta i dimezzamenti che restano. La macchina non sa quale nodo sia $z$ , quindi li prova tutti, uno dopo l'altro.

Dimostra la correttezza. La correttezza si prova per induzione su i, e il disegno mostra il passo induttivo. Letto dal basso in alto, un cammino da x a y lungo al più 2ⁱ si spezza nel nodo di mezzo z in due parti lunghe al più 2ⁱ⁻¹ (5 archi diventano 3 e 2, per questo si dice "al più"). Letto dall'alto in basso, due metà valide si attaccano in un cammino di al più 2 · 2ⁱ⁻¹ = 2ⁱ archi. — 4. Dimostra la correttezza
La correttezza si prova per induzione su $i$ , e il disegno mostra il passo induttivo. Letto dal basso in alto, un cammino da $x$ a $y$ lungo al più $2^i$ si spezza nel nodo di mezzo $z$ in due parti lunghe al più $2^{i-1}$ (5 archi diventano 3 e 2, per questo si dice "al più"). Letto dall'alto in basso, due metà valide si attaccano in un cammino di al più $2 \cdot 2^{i-1} = 2^i$ archi.

Riusa la memoria. Per ogni candidato z₁, z₂, z₃, … la chiamata solve(x, y, i) lancia due chiamate con i-1, una dopo l'altra, sulla stessa porzione di nastro. Quando una chiamata termina, i suoi dati si cancellano: i riquadri tratteggiati vuoti sono lo spazio liberato, che il tentativo successivo riusa. Per sapere da dove ripartire basta l'ultimo z provato, senza tenere l'elenco di quelli scartati. — 5. Riusa la memoria
Per ogni candidato $z_1, z_2, z_3, \dots$ la chiamata $\mathrm{solve}(x, y, i)$ lancia due chiamate con $i-1$ , una dopo l'altra, sulla stessa porzione di nastro. Quando una chiamata termina, i suoi dati si cancellano: i riquadri tratteggiati vuoti sono lo spazio liberato, che il tentativo successivo riusa. Per sapere da dove ripartire basta l'ultimo $z$ provato, senza tenere l'elenco di quelli scartati.

Conta pila e record. Su un grafo con v vertici la pila ha un livello per ogni valore di i, da ⌈ log v ⌉ fino a 0, quindi O(log v) livelli. Ogni livello è un record con x, y, z e i, numeri non più grandi di v, cioè O(log v) bit. Il prodotto è O(log² v), e i due log v hanno origini diverse: il primo conta i dimezzamenti, il secondo i bit del nome di un nodo. — 6. Conta pila e record
Su un grafo con $v$ vertici la pila ha un livello per ogni valore di $i$ , da $\lceil \log v \rceil$ fino a 0, quindi $O(\log v)$ livelli. Ogni livello è un record con $x$ , $y$ , $z$ e $i$ , numeri non più grandi di $v$ , cioè $O(\log v)$ bit. Il prodotto è $O(\log^2 v)$ , e i due $\log v$ hanno origini diverse: il primo conta i dimezzamenti, il secondo i bit del nome di un nodo.

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove: dispensa cap. 11, p. 30; slide Lez. 5

corollario

Corollario di Savitch (spazio nondeterministico)

chiesto in 7 domandedimostrato nel corso

Per ogni funzione propria $f(n) \ge \log n$ : $\mathrm{NSPACE}(f(n)) \subseteq \mathrm{SPACE}(f(n)^2)$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

Si applica l'algoritmo di Savitch al grafo delle configurazioni, che ha $c^{f(n)}$ nodi: $\log^2(c^{f(n)}) = O(f(n)^2)$ .

All'esame

Togliere il nondeterminismo costa solo un quadrato nello spazio, mentre nel tempo (per quanto si sa) costa un esponenziale.

Da scrivere all'esame

SÌ, per il corollario di Savitch $\mathrm{NSPACE}(f(n)) \subseteq \mathrm{SPACE}(f(n)^2)$ per $f(n) \ge \log n$ propria; per esempio $\htmlData{term=NL}{\mathrm{NL}} \subseteq \mathrm{SPACE}(\log^2 n)$ .

Dimostrazione illustrata

1 / 4

Il grafo implicito delle configurazioni. La nuvola tratteggiata è il grafo delle configurazioni di N su x. s è la configurazione iniziale e t, il doppio cerchio, l'unica che accetta, perché si può supporre che N prima di accettare cancelli i nastri e riporti le testine all'inizio. Con f(n) ≥ log n i nodi sono al più c^(log n + f(n)) ≤ (c²)^(f(n)), cioè |V| ≤ 2^(O(f(n))): troppi per scriverli tutti. — 1. Il grafo implicito delle configurazioni
La nuvola tratteggiata è il grafo delle configurazioni di $N$ su $x$ . $s$ è la configurazione iniziale e $t$ , il doppio cerchio, l'unica che accetta, perché si può supporre che $N$ prima di accettare cancelli i nastri e riporti le testine all'inizio. Con $f(n) \ge \log n$ i nodi sono al più $c^{\log n + f(n)} \le (c^2)^{f(n)}$ , cioè $|V| \le 2^{O(f(n))}$ : troppi per scriverli tutti.

Riconosci gli archi localmente. Nel caso base Savitch chiede se (C, C') è un arco, e qui non c'è una matrice di adiacenza da leggere. La macchina controlla se una mossa di N porta da C a C': legge il simbolo di x sotto la testina indicata da C, consulta la relazione di transizione Δ e confronta le due configurazioni, che differiscono solo nello stato e attorno alla testina (qui la a diventa b). Basta spazio O(f(n)). — 2. Riconosci gli archi localmente
Nel caso base Savitch chiede se $(C, C')$ è un arco, e qui non c'è una matrice di adiacenza da leggere. La macchina controlla se una mossa di $N$ porta da $C$ a $C'$ : legge il simbolo di $x$ sotto la testina indicata da $C$ , consulta la relazione di transizione $\Delta$ e confronta le due configurazioni, che differiscono solo nello stato e attorno alla testina (qui la $a$ diventa $b$ ). Basta spazio $O(f(n))$ .

Sostituisci il numero di nodi. Da V ≤ (c²)^(f(n)) viene log V ≤ 2 f(n) log c = O(f(n)), quindi O(log² V) = O(f(n)²): la pila ha O(f(n)) livelli da O(f(n)) simboli. Lo spazio O(f(n)) per controllare gli archi si somma senza cambiare l'ordine. Si ottiene NSPACE(f(n)) ⊆ SPACE(f(n)²), e con f(n) = log n si ha NL ⊆ SPACE(log² n). — 4. Sostituisci il numero di nodi
Da $V \le (c^2)^{f(n)}$ viene $\log V \le 2 f(n) \log c = O(f(n))$ , quindi $O(\log^2 V) = O(f(n)^2)$ : la pila ha $O(f(n))$ livelli da $O(f(n))$ simboli. Lo spazio $O(f(n))$ per controllare gli archi si somma senza cambiare l'ordine. Si ottiene $\mathrm{NSPACE}(f(n)) \subseteq \mathrm{SPACE}(f(n)^2)$ , e con $f(n) = \log n$ si ha $\htmlData{term=NL}{\mathrm{NL}} \subseteq \mathrm{SPACE}(\log^2 n)$ .

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F08 n. 2 · F13 n. 5 · F13 n. 7 · G20v3 n. 4 · FE23 n. 6 · E26 n. 1 · ND n. 1

Classi

NL PSPACE

Dove: dispensa cap. 11, p. 31; slide Lez. 5

corollario

Corollario: $\htmlData{term=PSPACE}{\mathrm{PSPACE}} = \mathrm{NPSPACE}$

chiesto in 7 domandedimostrato nel corso

$\htmlData{term=PSPACE}{\mathrm{PSPACE}} = \mathrm{NPSPACE}$ : il nondeterminismo non aggiunge problemi risolubili in spazio polinomiale.

Idea, frase per l'esame e dimostrazione +

Intuizione

Il quadrato di un polinomio è ancora un polinomio.

All'esame

Serve a rispondere SÌ a " $\mathrm{NPSPACE} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}}$ ?" e a dire che un problema PSPACE-completo e uno NPSPACE-completo si riducono l'uno all'altro.

Da scrivere all'esame

SÌ: $\mathrm{NPSPACE} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}}$ per il corollario di Savitch ( $\mathrm{NSPACE}(n^k) \subseteq \mathrm{SPACE}(n^{2k})$ ), quindi $\htmlData{term=PSPACE}{\mathrm{PSPACE}} = \mathrm{NPSPACE}$ .

Dimostrazione illustrata

1 / 3

Un'inclusione è immediata. L'ovale di PSPACE sta dentro quello di NPSPACE per il Teorema 7.4 (a): una macchina deterministica è una nondeterministica con una sola scelta per passo, e usa le stesse celle. Quindi SPACE(nᵏ) ⊆ NSPACE(nᵏ) per ogni k, e lo stesso vale per le unioni. — 1. Un'inclusione è immediata
L'ovale di $\htmlData{term=PSPACE}{\mathrm{PSPACE}}$ sta dentro quello di $\mathrm{NPSPACE}$ per il Teorema 7.4 (a): una macchina deterministica è una nondeterministica con una sola scelta per passo, e usa le stesse celle. Quindi $\mathrm{SPACE}(n^k) \subseteq \mathrm{NSPACE}(n^k)$ per ogni $k$ , e lo stesso vale per le unioni.

Resta nella stessa famiglia. (nᵏ)² = n²ᵏ è ancora un polinomio: spazio nondeterministico n³, per esempio, diventa spazio deterministico n⁶. Quindi L ∈ SPACE(n²ᵏ) ⊆ PSPACE, e con PSPACE ⊆ NPSPACE le due classi coincidono. Per il tempo non c'è un risultato simile, e la domanda su P e NP resta aperta. — 3. Resta nella stessa famiglia
$(n^k)^2 = n^{2k}$ è ancora un polinomio: spazio nondeterministico $n^3$ , per esempio, diventa spazio deterministico $n^6$ . Quindi $L \in \mathrm{SPACE}(n^{2k}) \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}}$ , e con $\htmlData{term=PSPACE}{\mathrm{PSPACE}} \subseteq \mathrm{NPSPACE}$ le due classi coincidono. Per il tempo non c'è un risultato simile, e la domanda su $\htmlData{term=P}{\mathrm{P}}$ e $\htmlData{term=NP}{\mathrm{NP}}$ resta aperta.

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F13 n. 7 · F14 n. 3 · LU22 n. 4 · FE23 n. 5 · MA23 n. 1 · E26 n. 7 · ND n. 1

Classi

PSPACE

Dove: dispensa cap. 11, p. 32; dispensa cap. 14, p. 57 (esercizio 3); slide Lez. 5

Capitolo 12 · Riduzioni (Cook-Levin)

proposizione

Proposizione (composizione di riduzioni)

chiesto in 3 domandedimostrato nel corso

Se $R$ è una riduzione da $L_1$ a $L_2$ e $R'$ è una riduzione da $L_2$ a $L_3$ , allora $R' \circ R$ è una riduzione da $L_1$ a $L_3$ (ancora in spazio logaritmico).

Idea, frase per l'esame e dimostrazione +

Intuizione

$R(x)$ non si scrive per intero: ogni volta che serve un suo simbolo lo si ricalcola, tenendo solo un contatore di $O(\log n)$ bit.

All'esame

Le riduzioni sono transitive: per mostrare che $B$ è NP-completo basta ridurre a $B$ un problema già NP-completo.

Da scrivere all'esame

SÌ, perché le riduzioni (in spazio logaritmico) si compongono: se $L_1$ si riduce a $L_2$ e $L_2$ a $L_3$ , allora $L_1$ si riduce a $L_3$ .

Dimostrazione illustrata

1 / 4

Concatena le equivalenze. R riduce A a B e S riduce B a C, quindi x ∈ A ⇔ R(x) ∈ B ⇔ S(R(x)) ∈ C. La composizione dà sempre la risposta giusta; resta da vedere se S(R(x)) si calcola ancora in spazio logaritmico. — 1. Concatena le equivalenze
$R$ riduce $A$ a $B$ e $S$ riduce $B$ a $C$ , quindi $x \in A \iff R(x) \in B \iff S(R(x)) \in C$ . La composizione dà sempre la risposta giusta; resta da vedere se $S(R(x))$ si calcola ancora in spazio logaritmico.

Ricalcola il simbolo richiesto. La macchina composta simula S e tiene solo l'indice i del simbolo di R(x) che S sta leggendo. Quando serve σᵢ, a sinistra si riesegue R su x contando i simboli prodotti senza scriverli, finché esce l'i-esimo; a destra S lo legge (la cella verde) e fa la sua mossa. Se S torna indietro, R riparte da capo, perché produce l'output solo in avanti. — 3. Ricalcola il simbolo richiesto
La macchina composta simula $S$ e tiene solo l'indice $i$ del simbolo di $R(x)$ che $S$ sta leggendo. Quando serve $\sigma_i$ , a sinistra si riesegue $R$ su $x$ contando i simboli prodotti senza scriverli, finché esce l' $i$ -esimo; a destra $S$ lo legge (la cella verde) e fa la sua mossa. Se $S$ torna indietro, $R$ riparte da capo, perché produce l'output solo in avanti.

Somma contatore e memorie. L'indice i arriva al più a |R(x)| ≤ n^c, quindi occupa O(log n^c) = O(log n) bit. La memoria di R è logaritmica in |x| = n. Quella di S è logaritmica nella lunghezza del suo input R(x), cioè O(log n^c) = O(log n). La somma è O(log n), e S ∘ R è ancora una riduzione in spazio logaritmico; i ricalcoli allungano il tempo, che resta polinomiale. — 4. Somma contatore e memorie
L'indice $i$ arriva al più a $|R(x)| \le n^c$ , quindi occupa $O(\log n^c) = O(\log n)$ bit. La memoria di $R$ è logaritmica in $|x| = n$ . Quella di $S$ è logaritmica nella lunghezza del suo input $R(x)$ , cioè $O(\log n^c) = O(\log n)$ . La somma è $O(\log n)$ , e $S \circ R$ è ancora una riduzione in spazio logaritmico; i ricalcoli allungano il tempo, che resta polinomiale.

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F02 n. 2 · MZ22 n. 6 · LU22 n. 3

Dove: dispensa cap. 12, p. 34

proposizione

Proposizione (un problema completo per due classi)

per l'oraledimostrato nel corso

Se $C_1$ e $C_2$ sono chiuse rispetto alle riduzioni e un linguaggio $L$ è completo per entrambe, allora $C_1 = C_2$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

Ogni problema di $C_1$ si riduce a $L$ , che sta in $C_2$ , quindi sta in $C_2$ ; e viceversa.

All'esame

Per esempio: un problema sia NP-completo sia coNP-completo darebbe $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}}$ .

Da scrivere all'esame

Solo se $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}}$ : un linguaggio completo per due classi chiuse rispetto alle riduzioni le fa coincidere.

Dimostrazione illustrata

1 / 3

Usa la prima completezza. Prendi A ∈ C₁. B è C₁-completo, quindi A si riduce a B, la freccia A ≤ B. B è anche C₂-completo, e in particolare sta in C₂; siccome C₂ è chiusa, la riduzione porta A in C₂. Vale per ogni A di C₁, quindi C₁ ⊆ C₂. — 1. Usa la prima completezza
Prendi $A \in C_1$ . $B$ è $C_1$ -completo, quindi $A$ si riduce a $B$ , la freccia $A \le B$ . $B$ è anche $C_2$ -completo, e in particolare sta in $C_2$ ; siccome $C_2$ è chiusa, la riduzione porta $A$ in $C_2$ . Vale per ogni $A$ di $C_1$ , quindi $C_1 \subseteq C_2$ .

Unisci le inclusioni. Le due frecce sono le inclusioni appena dimostrate, e insieme danno C₁ = C₂. Ognuna ha usato la difficoltà di B rispetto a una classe, la sua appartenenza all'altra e la chiusura di quest'ultima. Per esempio NP e coNP sono chiuse, quindi un problema sia NP-completo sia coNP-completo darebbe NP = coNP. — 3. Unisci le inclusioni
Le due frecce sono le inclusioni appena dimostrate, e insieme danno $C_1 = C_2$ . Ognuna ha usato la difficoltà di $B$ rispetto a una classe, la sua appartenenza all'altra e la chiusura di quest'ultima. Per esempio $\htmlData{term=NP}{\mathrm{NP}}$ e $\htmlData{term=coNP}{\mathrm{coNP}}$ sono chiuse, quindi un problema sia $\htmlData{term=NP}{\mathrm{NP}}$ -completo sia $\htmlData{term=coNP}{\mathrm{coNP}}$ -completo darebbe $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}}$ .

Scorri l'immagine o usa Avanti.

Dimostrazione

Classi

Dove: dispensa cap. 12, p. 35

corollario

Corollario (classe piccola con un problema completo per la grande)

per l'oraledimostrato nel corso

Se $C_1 \subseteq C_2$ , $C_1$ è chiusa rispetto alle riduzioni e contiene un problema $C_2$ -completo, allora $C_1 = C_2$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

Tutto $C_2$ si riduce a quel problema, e la chiusura di $C_1$ porta tutto dentro $C_1$ .

All'esame

Per esempio: un problema NP-completo sta in P solo se $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ ; QSAT sta in NP solo se $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=PSPACE}{\mathrm{PSPACE}}$ .

Da scrivere all'esame

Solo se $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ : $\htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=NP}{\mathrm{NP}}$ ed è chiusa rispetto alle riduzioni, quindi se contenesse un problema NP-completo sarebbe $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ .

Dimostrazione illustrata

1 / 3

Il problema completo nella classe piccola. In alto c'è l'ipotesi C₁ ⊆ C₂. Il problema B sta nella classe piccola C₁ ed è C₂-completo, e C₁ è chiusa per le riduzioni, il riquadro tratteggiato. Serve la chiusura della classe piccola, perché è dentro C₁ che bisogna portare i problemi; quella di C₂ non entra nella dimostrazione. — 1. Il problema completo nella classe piccola
In alto c'è l'ipotesi $C_1 \subseteq C_2$ . Il problema $B$ sta nella classe piccola $C_1$ ed è $C_2$ -completo, e $C_1$ è chiusa per le riduzioni, il riquadro tratteggiato. Serve la chiusura della classe piccola, perché è dentro $C_1$ che bisogna portare i problemi; quella di $C_2$ non entra nella dimostrazione.

Chiudi l'uguaglianza. Una freccia è l'ipotesi C₁ ⊆ C₂, l'altra l'inclusione C₂ ⊆ C₁ appena dimostrata: insieme danno C₁ = C₂. A differenza della proposizione sul problema completo per due classi, qui basta una sola completezza, perché la seconda inclusione è data. Nell'esempio sotto, P ⊆ NP e P è chiusa, quindi un problema NP-completo in P darebbe P = NP. — 3. Chiudi l'uguaglianza
Una freccia è l'ipotesi $C_1 \subseteq C_2$ , l'altra l'inclusione $C_2 \subseteq C_1$ appena dimostrata: insieme danno $C_1 = C_2$ . A differenza della proposizione sul problema completo per due classi, qui basta una sola completezza, perché la seconda inclusione è data. Nell'esempio sotto, $\htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=NP}{\mathrm{NP}}$ e $\htmlData{term=P}{\mathrm{P}}$ è chiusa, quindi un problema $\htmlData{term=NP}{\mathrm{NP}}$ -completo in $\htmlData{term=P}{\mathrm{P}}$ darebbe $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ .

Scorri l'immagine o usa Avanti.

Dimostrazione

Classi

P NP PSPACE

Dove: dispensa cap. 12, p. 36

teorema

Teorema di Cook-Levin

★ chiesto in 11 domandedimostrato nel corso

SAT è NP-completo.

Idea, frase per l'esame e dimostrazione +

Intuizione

Una computazione nondeterministica polinomiale si descrive con una tabella $p(n) \times p(n)$ , e la tabella si scrive come una formula in CNF che è soddisfacibile se e solo se esiste una computazione che accetta.

All'esame

È il primo problema NP-completo: tutte le altre prove di NP-completezza partono da SAT con catene di riduzioni.

Da scrivere all'esame

SAT è NP-completo per il teorema di Cook-Levin: ogni problema in NP si riduce a SAT, e $\htmlData{term=problem:SAT}{\mathrm{SAT}} \in \htmlData{term=NP}{\mathrm{NP}}$ .

Dimostrazione illustrata

1 / 6

Verifica un assegnamento. SAT ∈ NP è la parte facile. Per la formula φ in alto si indovina un valore per ogni variabile, qui x₁ = 1, x₂ = 0, x₃ = 1, e lo si sostituisce nelle clausole: ognuna diventa una coppia di bit con almeno un 1, quindi è vera. Il controllo richiede tempo polinomiale nella lunghezza di φ. — 1. Verifica un assegnamento
$\htmlData{term=problem:SAT}{\mathrm{SAT}} \in \htmlData{term=NP}{\mathrm{NP}}$ è la parte facile. Per la formula $\phi$ in alto si indovina un valore per ogni variabile, qui $x_1 = 1$ , $x_2 = 0$ , $x_3 = 1$ , e lo si sostituisce nelle clausole: ognuna diventa una coppia di bit con almeno un 1, quindi è vera. Il controllo richiede tempo polinomiale nella lunghezza di $\phi$ .

Disegna la computazione come tabella. Sia M la macchina nondeterministica che decide L in tempo T = p(n). Una sua computazione su x diventa una tabella: ogni riga è la configurazione a un istante, ogni colonna una cella del nastro. La prima riga contiene l'input a b seguito da blank, l'ultima lo stato che accetta q_(acc). In T passi la testina percorre al più T celle, quindi bastano T colonne. — 2. Disegna la computazione come tabella
Sia $M$ la macchina nondeterministica che decide $L$ in tempo $T = p(n)$ . Una sua computazione su $x$ diventa una tabella: ogni riga è la configurazione a un istante, ogni colonna una cella del nastro. La prima riga contiene l'input $a\,b$ seguito da blank, l'ultima lo stato che accetta $q_{acc}$ . In $T$ passi la testina percorre al più $T$ celle, quindi bastano $T$ colonne.

Crea le variabili booleane. Le tre righe sono le tre famiglie di variabili, e la casella verde segna quella vera: al tempo t la cella i contiene σ (in alto), la testina è sulla cella i (in mezzo), lo stato è q (in basso). Le clausole "esattamente uno" lasciano a ogni istante un solo simbolo per cella, una sola posizione della testina e un solo stato, così ogni riga è una configurazione. — 3. Crea le variabili booleane
Le tre righe sono le tre famiglie di variabili, e la casella verde segna quella vera: al tempo $t$ la cella $i$ contiene $\sigma$ (in alto), la testina è sulla cella $i$ (in mezzo), lo stato è $q$ (in basso). Le clausole "esattamente uno" lasciano a ogni istante un solo simbolo per cella, una sola posizione della testina e un solo stato, così ogni riga è una configurazione.

Imponi inizio, mosse e fine. Altre clausole legano la tabella a M e a x. La prima riga deve essere la configurazione iniziale, con l'input x₁ x₂ … seguito da blank. Fra due righe consecutive cambia solo la zona intorno alla testina, come prevede una mossa di Δ: al centro lo stato passa da q a q' mentre a e b restano dove sono. L'ultima riga deve contenere q_(acc). — 4. Imponi inizio, mosse e fine
Altre clausole legano la tabella a $M$ e a $x$ . La prima riga deve essere la configurazione iniziale, con l'input $x_1 x_2 \dots$ seguito da blank. Fra due righe consecutive cambia solo la zona intorno alla testina, come prevede una mossa di $\Delta$ : al centro lo stato passa da $q$ a $q'$ mentre $a$ e $b$ restano dove sono. L'ultima riga deve contenere $q_{acc}$ .

Prova i due versi. La freccia in alto va dalla tabella alla formula: se M accetta x, i valori che descrivono quella computazione rendono vere tutte le clausole di φ. Quella in basso va al contrario: un assegnamento che soddisfa φ riempie la tabella con una configurazione per riga, la prima iniziale, ognuna ottenuta dalla precedente con una mossa lecita e l'ultima con q_(acc), cioè con una computazione che accetta x. — 5. Prova i due versi
La freccia in alto va dalla tabella alla formula: se $M$ accetta $x$ , i valori che descrivono quella computazione rendono vere tutte le clausole di $\phi$ . Quella in basso va al contrario: un assegnamento che soddisfa $\phi$ riempie la tabella con una configurazione per riga, la prima iniziale, ognuna ottenuta dalla precedente con una mossa lecita e l'ultima con $q_{acc}$ , cioè con una computazione che accetta $x$ .

Conta la trasformazione. Le variabili sono O(T²), perché la tabella ha T² caselle e simboli e stati sono in numero costante. Le clausole sono O(T³): le più numerose vietano due posizioni della testina nello stesso istante, una per coppia di celle a ogni tempo. La riduzione le scrive con pochi contatori di O(log n) bit. Quindi ogni L ∈ NP si riduce a SAT, e poiché anche SAT ∈ NP, SAT è NP-completo. — 6. Conta la trasformazione
Le variabili sono $O(T^2)$ , perché la tabella ha $T^2$ caselle e simboli e stati sono in numero costante. Le clausole sono $O(T^3)$ : le più numerose vietano due posizioni della testina nello stesso istante, una per coppia di celle a ogni tempo. La riduzione le scrive con pochi contatori di $O(\log n)$ bit. Quindi ogni $L \in \htmlData{term=NP}{\mathrm{NP}}$ si riduce a SAT, e poiché anche $\htmlData{term=problem:SAT}{\mathrm{SAT}} \in \htmlData{term=NP}{\mathrm{NP}}$ , SAT è NP-completo.

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F04 n. 1 · F05 n. 6 · F12 n. 2 · F12 n. 5 · F13 n. 3 · F14 n. 6 · L18 n. 5 · GE23 n. 5 · FE23 n. 2 · SE23 n. 1 · ND n. 7

Classi

Problemi

SAT

Dove: dispensa cap. 12, p. 36. La dispensa dà anche la versione con i circuiti (ogni $L \in \htmlData{term=NP}{\mathrm{NP}}$ si riduce a CIRCUIT SAT, che si riduce a SAT); il riepilogo del cap. 22 elenca anche CIRCUIT SAT come NP-completo.

Capitolo 13 · Problemi in NP

proposizione

Proposizione 9.1 (certificati succinti)

chiesto in 4 domandedimostrato nel corso

$L \in \htmlData{term=NP}{\mathrm{NP}}$ se e solo se esiste una relazione $R$ decidibile in tempo polinomiale e polinomialmente bilanciata ( $|y| \le |x|^k$ ) tale che $L = \{x : (x, y) \in R \text{ per qualche } y\}$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

Il certificato $y$ è la registrazione di una computazione che accetta: è corto e si controlla in tempo polinomiale.

All'esame

Serve a dimostrare che un problema sta in NP ("indovina e verifica") e a scrivere un certificato succinto negli esercizi.

Da scrivere all'esame

Sta in NP per la Proposizione 9.1: ha un certificato di lunghezza polinomiale che si verifica in tempo polinomiale (indovina e verifica).

Dimostrazione illustrata

1 / 4

Da una computazione a un certificato. L'albero è la computazione della macchina nondeterministica N su x: a ogni nodo N sceglie una mossa, e il ramo verde arriva ad "accetta". Per descrivere quel ramo bastano le scelte fatte lungo la strada, al più |x|ᵏ se N lavora in tempo |x|ᵏ, e la graffa le indica come certificato y, che ha quindi lunghezza polinomiale in |x|. — 1. Da una computazione a un certificato
L'albero è la computazione della macchina nondeterministica $N$ su $x$ : a ogni nodo $N$ sceglie una mossa, e il ramo verde arriva ad "accetta". Per descrivere quel ramo bastano le scelte fatte lungo la strada, al più $|x|^k$ se $N$ lavora in tempo $|x|^k$ , e la graffa le indica come certificato $y$ , che ha quindi lunghezza polinomiale in $|x|$ .

Verifica il certificato. Il verificatore è deterministico: riceve x e y, riesegue N su x seguendo le scelte scritte in y e accetta se quel ramo finisce in "yes", altrimenti rifiuta. I due riquadri rosa sono le condizioni della proposizione: y ha lunghezza polinomiale in |x|, e il controllo richiede tempo polinomiale perché il ramo ha al più |x|ᵏ passi. — 2. Verifica il certificato
Il verificatore è deterministico: riceve $x$ e $y$ , riesegue $N$ su $x$ seguendo le scelte scritte in $y$ e accetta se quel ramo finisce in "yes", altrimenti rifiuta. I due riquadri rosa sono le condizioni della proposizione: $y$ ha lunghezza polinomiale in $|x|$ , e il controllo richiede tempo polinomiale perché il ramo ha al più $|x|^k$ passi.

Dal verificatore alla macchina NP. Nel verso opposto si parte dal verificatore. La macchina nondeterministica, su input x, scrive un simbolo alla volta una stringa y lunga al più |x|ᵏ, e ogni ramo ne scrive una diversa; poi esegue il verificatore su (x, y) e accetta se il verificatore accetta. Il tempo totale è polinomiale in |x| grazie al limite su |y|: con certificati lunghi a piacere non lo sarebbe. — 3. Dal verificatore alla macchina NP
Nel verso opposto si parte dal verificatore. La macchina nondeterministica, su input $x$ , scrive un simbolo alla volta una stringa $y$ lunga al più $|x|^k$ , e ogni ramo ne scrive una diversa; poi esegue il verificatore su $(x, y)$ e accetta se il verificatore accetta. Il tempo totale è polinomiale in $|x|$ grazie al limite su $|y|$ : con certificati lunghi a piacere non lo sarebbe.

Concludi l'equivalenza. A sinistra un ramo che accetta x, a destra un certificato y con V(x, y) = 1, cioè con (x, y) ∈ R. Le due costruzioni passano dall'uno all'altro in entrambi i versi, quindi x ∈ L se e solo se esiste un y che il verificatore accetta. Per mostrare che un problema sta in NP basta allora un certificato corto e un controllo polinomiale. — 4. Concludi l'equivalenza
A sinistra un ramo che accetta $x$ , a destra un certificato $y$ con $V(x, y) = 1$ , cioè con $(x, y) \in R$ . Le due costruzioni passano dall'uno all'altro in entrambi i versi, quindi $x \in L$ se e solo se esiste un $y$ che il verificatore accetta. Per mostrare che un problema sta in NP basta allora un certificato corto e un controllo polinomiale.

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F03 n. 4 · F14 n. 4 · LU24 n. 4 · SP n. 4

Classi

Dove: dispensa cap. 13, p. 40

teorema

MAX2SAT è NP-completo

per l'oraledimostrato nel corso

Dato un insieme di clausole con 2 letterali e un intero $K$ , decidere se si possono soddisfare almeno $K$ clausole è NP-completo.

Idea, frase per l'esame e dimostrazione +

Intuizione

Ogni clausola di 3SAT diventa un gruppo di 10 clausole di 2 letterali: se ne soddisfano al più 7, e 7 esattamente quando la clausola originale è vera (obiettivo $K = 7m$ ).

All'esame

Mostra che 2-SAT è facile ma la sua versione di massimizzazione è difficile.

Da scrivere all'esame

MAX2SAT è NP-completo (riduzione da 3SAT: 10 clausole per ogni clausola, obiettivo $K = 7m$ ), anche se $\htmlData{term=problem:SAT2}{\mathrm{2\text{-}SAT}} \in \htmlData{term=P}{\mathrm{P}}$ .

Dimostrazione illustrata

1 / 5

Controlla l'appartenenza. Un'istanza di MAX2SAT è un elenco di clausole con al più due letterali e un intero K. Il certificato è un assegnamento, come x₁ = 1, x₂ = 0, x₃ = 1: si valuta ogni clausola, si contano quelle vere (qui due, perché (¬ x₁ ∨ ¬ x₃) è falsa) e si confronta il conto con K, in tempo polinomiale. — 1. Controlla l'appartenenza
Un'istanza di MAX2SAT è un elenco di clausole con al più due letterali e un intero $K$ . Il certificato è un assegnamento, come $x_1 = 1$ , $x_2 = 0$ , $x_3 = 1$ : si valuta ogni clausola, si contano quelle vere (qui due, perché $(\neg x_1 \lor \neg x_3)$ è falsa) e si confronta il conto con $K$ , in tempo polinomiale.

Sostituisci una clausola di 3-SAT. La clausola (x ∨ y ∨ z) diventa le dieci clausole del riquadro: quattro di un solo letterale, (x), (y), (z), (a); tre come (¬ x ∨ ¬ y), false quando due letterali sono veri insieme; tre come (x ∨ ¬ a). La variabile a, a sinistra, è nuova, e ogni clausola originale ne ha una sua, perché il valore migliore di a dipende dalla clausola. — 2. Sostituisci una clausola di 3-SAT
La clausola $(x \lor y \lor z)$ diventa le dieci clausole del riquadro: quattro di un solo letterale, $(x)$ , $(y)$ , $(z)$ , $(a)$ ; tre come $(\neg x \lor \neg y)$ , false quando due letterali sono veri insieme; tre come $(x \lor \neg a)$ . La variabile $a$ , a sinistra, è nuova, e ogni clausola originale ne ha una sua, perché il valore migliore di $a$ dipende dalla clausola.

Conta le clausole vere. Scegliendo a nel modo migliore, il gruppo dà esattamente 7 clausole vere se (x ∨ y ∨ z) è vera e al più 6 se è falsa; più di 7 mai. Per esempio, con un solo letterale vero e a falsa sono vere una clausola fra (x), (y), (z), le tre coppie negate e le tre clausole con ¬ a: 7. Con tutti e tre falsi il massimo è 6. — 3. Conta le clausole vere
Scegliendo $a$ nel modo migliore, il gruppo dà esattamente 7 clausole vere se $(x \lor y \lor z)$ è vera e al più 6 se è falsa; più di 7 mai. Per esempio, con un solo letterale vero e $a$ falsa sono vere una clausola fra $(x)$ , $(y)$ , $(z)$ , le tre coppie negate e le tre clausole con $\neg a$ : 7. Con tutti e tre falsi il massimo è 6.

Scorri l'immagine o usa Avanti.

Dimostrazione

Classi

Problemi

MAX2SAT

Dove: dispensa cap. 13, p. 41

teorema

INDEPENDENT SET è NP-completo

per l'oraledimostrato nel corso

Dato un grafo $G$ e un intero $K$ , decidere se $G$ ha un insieme indipendente di $K$ nodi è NP-completo.

Idea, frase per l'esame e dimostrazione +

Intuizione

Riduzione da 3SAT: un triangolo per ogni clausola e un arco tra letterali opposti; un insieme indipendente di $m$ nodi sceglie un letterale vero per clausola.

All'esame

È il punto di partenza per CLIQUE e NODE COVER.

Da scrivere all'esame

INDEPENDENT SET è NP-completo (riduzione da 3SAT: un triangolo per clausola, archi tra letterali opposti, $K = m$ ).

Dimostrazione illustrata

1 / 4

Verifica un gruppo di vertici. Il certificato è l'insieme S di K nodi, in verde nel grafo. Il verificatore prende le coppie di nodi di S, come (v₁, v₂) e (v₁, v₃), e controlla che nessuna sia un arco. Le coppie sono meno di K², quindi basta tempo polinomiale e INDEPENDENT SET sta in NP. — 1. Verifica un gruppo di vertici
Il certificato è l'insieme $S$ di $K$ nodi, in verde nel grafo. Il verificatore prende le coppie di nodi di $S$ , come $(v_1, v_2)$ e $(v_1, v_3)$ , e controlla che nessuna sia un arco. Le coppie sono meno di $K^2$ , quindi basta tempo polinomiale e INDEPENDENT SET sta in NP.

Imposta K al numero di clausole. Con m clausole ci sono m triangoli, e l'obiettivo è K = m. Un insieme indipendente di m nodi ne prende esattamente uno per triangolo, il nodo verde, senza letterali opposti: rendendo veri quei letterali si soddisfa la formula. Viceversa, da un assegnamento che la soddisfa si prende un letterale vero per clausola. Il grafo ha 3m nodi e si costruisce in spazio logaritmico. — 4. Imposta K al numero di clausole
Con $m$ clausole ci sono $m$ triangoli, e l'obiettivo è $K = m$ . Un insieme indipendente di $m$ nodi ne prende esattamente uno per triangolo, il nodo verde, senza letterali opposti: rendendo veri quei letterali si soddisfa la formula. Viceversa, da un assegnamento che la soddisfa si prende un letterale vero per clausola. Il grafo ha $3m$ nodi e si costruisce in spazio logaritmico.

Scorri l'immagine o usa Avanti.

Dimostrazione

Classi

Problemi

INDEPENDENT SET

Dove: dispensa cap. 13, p. 42

corollario

Corollario: CLIQUE e NODE COVER sono NP-completi

★ chiesto in 8 domandedimostrato nel corso

CLIQUE e NODE COVER sono NP-completi.

Idea, frase per l'esame e dimostrazione +

Intuizione

Una cricca di $G$ è un insieme indipendente del grafo complementare; $I$ è indipendente se e solo se $V - I$ è una copertura dei nodi.

All'esame

CLIQUE è il problema NP-completo più usato negli esercizi sulle riduzioni.

Da scrivere all'esame

CLIQUE e NODE COVER sono NP-completi: una cricca di $G$ è un insieme indipendente del grafo complementare, e $I$ è indipendente se e solo se $V - I$ è una copertura dei nodi.

Dimostrazione illustrata

1 / 4

Parti da INDEPENDENT SET. INDEPENDENT SET chiede se G ha K nodi senza archi fra loro, ed è NP-completo. Nel ciclo di quattro nodi del disegno S = 1, 3 è indipendente, con |S| = 2, perché 1 e 3 non sono collegati. Per CLIQUE e NODE COVER basta riscrivere un'istanza come questa, senza costruire gadget nuovi da 3SAT. — 1. Parti da INDEPENDENT SET
INDEPENDENT SET chiede se $G$ ha $K$ nodi senza archi fra loro, ed è NP-completo. Nel ciclo di quattro nodi del disegno $S = \{1, 3\}$ è indipendente, con $|S| = 2$ , perché 1 e 3 non sono collegati. Per CLIQUE e NODE COVER basta riscrivere un'istanza come questa, senza costruire gadget nuovi da 3SAT.

Per CLIQUE cambia gli archi. A destra c'è il complementare Ḡ: stessi nodi, e un arco fra due nodi distinti esattamente quando in G manca. I lati del quadrato spariscono e compaiono le diagonali [1, 3] e [2, 4]. Ora 1 e 3 sono collegati, quindi S = 1, 3 è una cricca di Ḡ. La riduzione manda (G, K) in (Ḡ, K). — 2. Per CLIQUE cambia gli archi
A destra c'è il complementare $\bar G$ : stessi nodi, e un arco fra due nodi distinti esattamente quando in $G$ manca. I lati del quadrato spariscono e compaiono le diagonali $[1, 3]$ e $[2, 4]$ . Ora 1 e 3 sono collegati, quindi $S = \{1, 3\}$ è una cricca di $\bar G$ . La riduzione manda $(G, K)$ in $(\bar G, K)$ .

Per NODE COVER cambia l'insieme. Qui il grafo resta G e si prende il complemento dell'insieme: C = V ∖ S = 2, 4, in verde. Ogni lato del quadrato ha un estremo in 2 o in 4, quindi C è una copertura. In generale un arco resta scoperto da V ∖ S solo se ha entrambi gli estremi in S, cioè se S non è indipendente. Il budget diventa n - K, qui 4 - 2 = 2. — 3. Per NODE COVER cambia l'insieme
Qui il grafo resta $G$ e si prende il complemento dell'insieme: $C = V \setminus S = \{2, 4\}$ , in verde. Ogni lato del quadrato ha un estremo in 2 o in 4, quindi $C$ è una copertura. In generale un arco resta scoperto da $V \setminus S$ solo se ha entrambi gli estremi in $S$ , cioè se $S$ non è indipendente. Il budget diventa $n - K$ , qui $4 - 2 = 2$ .

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F02 n. 3 · F04 n. 1 · F04 n. 2 · F07 n. 6 · L18 n. 6 · G20v4 n. 7 · ND n. 6 · SP n. 4

Classi

Problemi

CLIQUE · NODE COVER

Dove: dispensa cap. 13, p. 44

teorema

TSP(D) è NP-completo

chiesto in 5 domandedimostrato nel corso

Data una matrice delle distanze tra $n$ città e un budget $B$ , decidere se esiste un giro di tutte le città di costo al più $B$ è NP-completo.

Idea, frase per l'esame e dimostrazione +

Intuizione

Ogni nodo del grafo diventa una città, a distanza 1 se c'è l'arco e 2 se non c'è: un giro di costo $n$ esiste se e solo se il grafo ha un ciclo hamiltoniano.

All'esame

Problema NP-completo ricorrente; servono solo distanze 1 e 2, quindi è NP-completo in senso forte.

Da scrivere all'esame

TSP(D) è NP-completo, anche in senso forte: HAMILTON CYCLE vi si riduce con distanza 1 sugli archi, 2 altrove e budget $B = n$ .

Dimostrazione illustrata

1 / 4

Controlla un giro. Il certificato è un giro, cioè un ordine v₁, …, v_n delle città che alla fine torna alla prima, come nel disegno. Il verificatore controlla che ogni città compaia una volta, somma le n distanze d(vᵢ, vᵢ₊₁), con v_(n+1) = v₁ per la tratta di ritorno, e confronta il costo con B. Sono controlli polinomiali, quindi TSP(D) sta in NP. — 1. Controlla un giro
Il certificato è un giro, cioè un ordine $v_1, \dots, v_n$ delle città che alla fine torna alla prima, come nel disegno. Il verificatore controlla che ogni città compaia una volta, somma le $n$ distanze $d(v_i, v_{i+1})$ , con $v_{n+1} = v_1$ per la tratta di ritorno, e confronta il costo con $B$ . Sono controlli polinomiali, quindi TSP(D) sta in NP.

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F03 n. 2 · F08 n. 7 · F14 n. 2 · F14 n. 4 · F14 n. 7

Classi

Problemi

TSP(D) · HAMILTON PATH

Dove: dispensa cap. 13, p. 44

teorema

3-COLORING è NP-completo ( $\mathrm{2\text{-}COLORING} \in \htmlData{term=P}{\mathrm{P}}$ )

★ chiesto in 10 domandedimostrato nel corso

Decidere se un grafo si colora con 3 colori senza nodi adiacenti dello stesso colore è NP-completo; con 2 colori il problema è in P.

Idea, frase per l'esame e dimostrazione +

Intuizione

Riduzione da 3SAT con due gadget: uno codifica il valore vero/falso dei letterali, l'altro l'OR di una clausola.

All'esame

Esempio classico del salto da 2 a 3: 2-COLORING in P, 3-COLORING NP-completo.

Da scrivere all'esame

3-COLORING è NP-completo (riduzione da 3SAT con un gadget per i valori di verità e un gadget OR), mentre 2-COLORING è in P.

Dimostrazione illustrata

1 / 5

Controlla i colori. Il certificato assegna un colore a ogni nodo. Il verificatore guarda gli archi uno alla volta e controlla che gli estremi abbiano colori diversi, come nel triangolo del disegno. Il controllo richiede tempo lineare nel numero di archi, quindi 3-COLORING sta in NP. — 1. Controlla i colori
Il certificato assegna un colore a ogni nodo. Il verificatore guarda gli archi uno alla volta e controlla che gli estremi abbiano colori diversi, come nel triangolo del disegno. Il controllo richiede tempo lineare nel numero di archi, quindi 3-COLORING sta in NP.

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F04 n. 3 · F12 n. 2 · F14 n. 1 · G20v1 n. 4 · MA23 n. 2 · MA23 n. 7 · SE23 n. 6 · LU24 n. 2 · ND n. 1 · ND n. 4

Classi

Problemi

2-COL · 3-COL

Dove: dispensa cap. 13, p. 44. Che 2-COLORING sia in P è solo affermato, senza prova.

corollario

Corollario: EXACT COVER BY 3-SETS, SET COVERING e SET PACKING sono NP-completi

per l'oraledimostrato nel corso

EXACT COVER BY 3-SETS, SET COVERING e SET PACKING sono NP-completi.

Idea, frase per l'esame e dimostrazione +

Intuizione

Sono tutti generalizzazioni di TRIPARTITE MATCHING: se un caso particolare è difficile, lo è anche il problema generale.

Da scrivere all'esame

EXACT COVER BY 3-SETS, SET COVERING e SET PACKING sono NP-completi perché generalizzano TRIPARTITE MATCHING, che è NP-completo.

Dimostrazione illustrata

1 / 4

Da terne a insiemi. Un'istanza di TRIPARTITE MATCHING diventa un'istanza di EXACT COVER BY 3-SETS. L'universo U contiene tutti gli elementi dei tre insiemi, tenuti distinti, e ogni terna (aᵢ, bᵢ, cᵢ) diventa l'insieme aᵢ, bᵢ, cᵢ. Un matching, cioè n terne senza componenti in comune, è allora fatto di n insiemi disgiunti che coprono i 3n elementi di U: una copertura esatta. — 1. Da terne a insiemi
Un'istanza di TRIPARTITE MATCHING diventa un'istanza di EXACT COVER BY 3-SETS. L'universo $U$ contiene tutti gli elementi dei tre insiemi, tenuti distinti, e ogni terna $(a_i, b_i, c_i)$ diventa l'insieme $\{a_i, b_i, c_i\}$ . Un matching, cioè $n$ terne senza componenti in comune, è allora fatto di $n$ insiemi disgiunti che coprono i $3n$ elementi di $U$ : una copertura esatta.

Da copertura esatta a SET COVERING. Si tiene la stessa famiglia di insiemi da 3 elementi su U = 1, …, 3m e si chiede una copertura con al più m insiemi. Al più m insiemi da 3 coprono al più 3m elementi, e arrivano a tutti solo se sono esattamente m e disgiunti, come i blocchi di tre elementi del disegno. Le coperture con budget m sono quindi le coperture esatte. — 2. Da copertura esatta a SET COVERING
Si tiene la stessa famiglia di insiemi da 3 elementi su $U = \{1, \dots, 3m\}$ e si chiede una copertura con al più $m$ insiemi. Al più $m$ insiemi da 3 coprono al più $3m$ elementi, e arrivano a tutti solo se sono esattamente $m$ e disgiunti, come i blocchi di tre elementi del disegno. Le coperture con budget $m$ sono quindi le coperture esatte.

Verifica e concludi. Il certificato è l'elenco degli insiemi scelti, e il verificatore controlla quello che chiede il problema: che abbiano 3 elementi, siano disgiunti e coprano U, e che il loro numero rispetti budget o obiettivo. Sono controlli polinomiali. TRIPARTITE MATCHING è NP-completo e si riduce a EXACT COVER BY 3-SETS, che si riduce agli altri due, quindi tutti e tre sono NP-completi. — 4. Verifica e concludi
Il certificato è l'elenco degli insiemi scelti, e il verificatore controlla quello che chiede il problema: che abbiano 3 elementi, siano disgiunti e coprano $U$ , e che il loro numero rispetti budget o obiettivo. Sono controlli polinomiali. TRIPARTITE MATCHING è NP-completo e si riduce a EXACT COVER BY 3-SETS, che si riduce agli altri due, quindi tutti e tre sono NP-completi.

Scorri l'immagine o usa Avanti.

Dimostrazione

Classi

Dove: dispensa cap. 13, p. 47

teorema

KNAPSACK è NP-completo

per l'oraledimostrato nel corso

Dati $n$ oggetti con peso e valore interi, un limite di peso $W$ e un obiettivo $K$ , decidere se si possono scegliere oggetti di peso totale $\le W$ e valore $\ge K$ è NP-completo.

Idea, frase per l'esame e dimostrazione +

Intuizione

Riduzione da EXACT COVER BY 3-SETS: ogni insieme diventa un numero scritto in base $n+1$ , così le somme non hanno riporti; servono però numeri esponenzialmente grandi.

All'esame

È l'unico NP-completo del capitolo che non lo è in senso forte.

Da scrivere all'esame

KNAPSACK è NP-completo (riduzione da EXACT COVER BY 3-SETS con numeri in base $n + 1$ ), ma non in senso forte: la riduzione crea numeri di valore esponenziale.

Dimostrazione illustrata

1 / 3

Controlla un sottoinsieme. Ogni oggetto i ha un peso wᵢ e un valore vᵢ. Il certificato è l'insieme S degli oggetti scelti: il verificatore somma pesi e valori e controlla ∑_(i ∈ S) wᵢ ≤ W e ∑_(i ∈ S) vᵢ ≥ K. Sono n addizioni e due confronti, in tempo polinomiale nella lunghezza dei numeri, quindi KNAPSACK sta in NP. — 1. Controlla un sottoinsieme
Ogni oggetto $i$ ha un peso $w_i$ e un valore $v_i$ . Il certificato è l'insieme $S$ degli oggetti scelti: il verificatore somma pesi e valori e controlla $\sum_{i \in S} w_i \le W$ e $\sum_{i \in S} v_i \ge K$ . Sono $n$ addizioni e due confronti, in tempo polinomiale nella lunghezza dei numeri, quindi KNAPSACK sta in NP.

Peso uguale al valore. Basta un caso particolare di KNAPSACK: ogni numero aᵢ diventa un oggetto con peso e valore uguali ad aᵢ, e limite e obiettivo coincidono, W = K = B. Se un problema NP-completo si riduce a queste istanze, KNAPSACK è NP-difficile. Nella prova i numeri aᵢ vengono da EXACT COVER BY 3-SETS: ogni insieme diventa un numero in base n + 1, con cifra 1 nelle posizioni dei suoi elementi. — 2. Peso uguale al valore
Basta un caso particolare di KNAPSACK: ogni numero $a_i$ diventa un oggetto con peso e valore uguali ad $a_i$ , e limite e obiettivo coincidono, $W = K = B$ . Se un problema NP-completo si riduce a queste istanze, KNAPSACK è NP-difficile. Nella prova i numeri $a_i$ vengono da EXACT COVER BY 3-SETS: ogni insieme diventa un numero in base $n + 1$ , con cifra 1 nelle posizioni dei suoi elementi.

Forza l'uguaglianza. Con wᵢ = vᵢ = aᵢ peso e valore sono la stessa somma, e le condizioni ≤ B e ≥ B insieme chiedono ∑_(i ∈ S) aᵢ = B. Con B fatto di sole cifre 1, la somma vale B solo se ogni elemento è coperto una volta: la base n + 1 evita i riporti. Questi numeri hanno però valore esponenziale, e la prova non dice niente sulle istanze con numeri piccoli. — 3. Forza l'uguaglianza
Con $w_i = v_i = a_i$ peso e valore sono la stessa somma, e le condizioni $\le B$ e $\ge B$ insieme chiedono $\sum_{i \in S} a_i = B$ . Con $B$ fatto di sole cifre 1, la somma vale $B$ solo se ogni elemento è coperto una volta: la base $n + 1$ evita i riporti. Questi numeri hanno però valore esponenziale, e la prova non dice niente sulle istanze con numeri piccoli.

Scorri l'immagine o usa Avanti.

Dimostrazione

Classi

Problemi

KNAPSACK

Dove: dispensa cap. 13, p. 48

proposizione

Proposizione (KNAPSACK in tempo $O(nW)$ )

per l'oraledimostrato nel corso

Ogni istanza di KNAPSACK si risolve in tempo $O(nW)$ , dove $n$ è il numero di oggetti e $W$ il limite di peso.

Idea, frase per l'esame e dimostrazione +

Intuizione

Programmazione dinamica su una tabella $n \times W$ ; ma $W$ può essere esponenziale nella lunghezza dell'input (circa $n \log W$ ), quindi l'algoritmo è solo pseudopolinomiale.

All'esame

Non dimostra $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ : il tempo è polinomiale nel valore dei numeri, non nella loro lunghezza.

Da scrivere all'esame

KNAPSACK si risolve in tempo $O(nW)$ , ma è un algoritmo pseudopolinomiale ( $W$ è esponenziale nella lunghezza dell'input), quindi non implica $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ .

Dimostrazione illustrata

1 / 4

Definisci il sottoproblema. La tabella ha una riga per ogni i da 0 a n e una colonna per ogni capacità w da 0 a W. La cella D[i, w] contiene il valore massimo che si ottiene scegliendo fra i primi i oggetti con peso totale al più w. La riga 0, evidenziata, è tutta di zeri: senza oggetti il valore è 0 per ogni capacità. — 1. Definisci il sottoproblema
La tabella ha una riga per ogni $i$ da $0$ a $n$ e una colonna per ogni capacità $w$ da $0$ a $W$ . La cella $D[i, w]$ contiene il valore massimo che si ottiene scegliendo fra i primi $i$ oggetti con peso totale al più $w$ . La riga $0$ , evidenziata, è tutta di zeri: senza oggetti il valore è $0$ per ogni capacità.

Confronta due possibilità. Una scelta ottima per D[i, w] o lascia fuori l'oggetto i o lo prende. Il riquadro blu è il primo caso: resta il meglio fra i primi i-1 oggetti, D[i-1, w]. Il riquadro verde è il secondo, possibile solo se il peso pᵢ non supera w: si guadagna il valore vᵢ e la capacità rimasta, w - pᵢ, va usata al meglio con gli altri oggetti. D[i, w] è il maggiore dei due. — 2. Confronta due possibilità
Una scelta ottima per $D[i, w]$ o lascia fuori l'oggetto $i$ o lo prende. Il riquadro blu è il primo caso: resta il meglio fra i primi $i-1$ oggetti, $D[i-1, w]$ . Il riquadro verde è il secondo, possibile solo se il peso $p_i$ non supera $w$ : si guadagna il valore $v_i$ e la capacità rimasta, $w - p_i$ , va usata al meglio con gli altri oggetti. $D[i, w]$ è il maggiore dei due.

Perché è solo pseudopolinomiale. In alto il segno ≠ separa O(nW) dal tempo polinomiale nella lunghezza dell'input. O(nW) è polinomiale nel valore di W, ma l'input è lungo circa n log W bit. Nel riquadro in basso W = 2^(m-1) si scrive con m bit e dà una tabella con 2^(m-1) + 1 colonne: il tempo è esponenziale nella lunghezza, e l'algoritmo non dimostra P = NP. — 4. Perché è solo pseudopolinomiale
In alto il segno $\ne$ separa $O(nW)$ dal tempo polinomiale nella lunghezza dell'input. $O(nW)$ è polinomiale nel valore di $W$ , ma l'input è lungo circa $n \log W$ bit. Nel riquadro in basso $W = 2^{m-1}$ si scrive con $m$ bit e dà una tabella con $2^{m-1} + 1$ colonne: il tempo è esponenziale nella lunghezza, e l'algoritmo non dimostra $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ .

Scorri l'immagine o usa Avanti.

Dimostrazione

Classi

Problemi

KNAPSACK

Dove: dispensa cap. 13, p. 49

Capitolo 14 · coNP

teorema

VALIDITY è coNP-completo

chiesto in 7 domandedimostrato nel corso

VALIDITY (la formula è vera per ogni assegnazione?) è coNP-completo; lo è anche HAMILTON PATH COMPLEMENT (il grafo non ha cammini hamiltoniani?).

Idea, frase per l'esame e dimostrazione +

Intuizione

Se $L \in \htmlData{term=coNP}{\mathrm{coNP}}$ , il suo complemento si riduce a SAT con una $R$ ; allora $R'(x) = \neg R(x)$ riduce $L$ a VALIDITY.

All'esame

È il coNP-completo di riferimento: per esempio una riduzione da SAT a VALIDITY esiste solo se $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}}$ .

Da scrivere all'esame

VALIDITY è coNP-completo (se $R$ riduce $\overline{L}$ a SAT, $R'(x) = \neg R(x)$ riduce $L$ a VALIDITY), quindi una riduzione da SAT a VALIDITY implicherebbe $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}}$ .

Dimostrazione illustrata

1 / 3

Cerca un controesempio. Una formula φ non è valida se esiste un assegnamento α che la rende falsa, cioè φ(α) = 0 (riquadro rosso). Dato α, basta valutare φ per controllarlo, in tempo polinomiale (riquadro verde). Il complemento di VALIDITY sta quindi in NP, e VALIDITY sta in coNP. — 1. Cerca un controesempio
Una formula $\varphi$ non è valida se esiste un assegnamento $\alpha$ che la rende falsa, cioè $\varphi(\alpha) = 0$ (riquadro rosso). Dato $\alpha$ , basta valutare $\varphi$ per controllarlo, in tempo polinomiale (riquadro verde). Il complemento di VALIDITY sta quindi in NP, e VALIDITY sta in coNP.

Nega la formula. φ è vera per ogni assegnamento se e solo se ¬φ è falsa per ogni assegnamento, cioè insoddisfacibile. Da qui viene la riduzione: se R riduce a SAT il complemento di un linguaggio L di coNP, allora R'(x) = ¬ R(x) riduce L a VALIDITY. VALIDITY però non è il complemento di SAT: la formula x non è valida e nemmeno insoddisfacibile. — 2. Nega la formula
$\varphi$ è vera per ogni assegnamento se e solo se $\neg\varphi$ è falsa per ogni assegnamento, cioè insoddisfacibile. Da qui viene la riduzione: se $R$ riduce a SAT il complemento di un linguaggio $L$ di coNP, allora $R'(x) = \neg R(x)$ riduce $L$ a VALIDITY. VALIDITY però non è il complemento di SAT: la formula $x$ non è valida e nemmeno insoddisfacibile.

Trasferisci la completezza. In alto, SAT è NP-completo e il suo complemento, scritto co-SAT, è coNP-completo: è il complemento del linguaggio, non la negazione di una formula. Con φ ↦ ¬φ co-SAT si riduce a VALIDITY, che quindi è coNP-completo. In basso lo stesso passaggio dà la coNP-completezza di co-HAMILTON PATH, il complemento di HAMILTON PATH, senza cambiare la riduzione. — 3. Trasferisci la completezza
In alto, SAT è NP-completo e il suo complemento, scritto co-SAT, è coNP-completo: è il complemento del linguaggio, non la negazione di una formula. Con $\varphi \mapsto \neg\varphi$ co-SAT si riduce a VALIDITY, che quindi è coNP-completo. In basso lo stesso passaggio dà la coNP-completezza di co-HAMILTON PATH, il complemento di HAMILTON PATH, senza cambiare la riduzione.

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F12 n. 2 · F12 n. 5 · F14 n. 2 · G20v2 n. 3 · LU22 n. 1 · SE23 n. 1 · ND n. 7

Classi

coNP

Problemi

VALIDITY · co-HAMILTON PATH

Dove: dispensa cap. 14, p. 53

proposizione

Proposizione A (riduzioni e complementi)

per l'oraledimostrato nel corso

Se $R$ è una riduzione da $L$ a $L'$ , allora $R$ è anche una riduzione dal complemento di $L$ al complemento di $L'$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

$x \in L \iff R(x) \in L'$ equivale a $x \notin L \iff R(x) \notin L'$ .

All'esame

Strumento per dimostrare le Proposizioni B, C e D.

Da scrivere all'esame

Per la Proposizione A, una riduzione $R$ da $L$ a $L'$ è anche una riduzione dal complemento di $L$ al complemento di $L'$ .

Dimostrazione illustrata

1 / 3

Parti dall'equivalenza. La riduzione R porta ogni stringa x (cerchio blu) nella stringa R(x) (cerchio verde). Che sia una riduzione da A a B lo dice la riga sotto: x ∈ A ⇔ R(x) ∈ B. Il "se e solo se" vale nei due versi, quindi R manda le istanze sì in istanze sì e anche le istanze no in istanze no. — 1. Parti dall'equivalenza
La riduzione $R$ porta ogni stringa $x$ (cerchio blu) nella stringa $R(x)$ (cerchio verde). Che sia una riduzione da $A$ a $B$ lo dice la riga sotto: $x \in A \iff R(x) \in B$ . Il "se e solo se" vale nei due versi, quindi $R$ manda le istanze sì in istanze sì e anche le istanze no in istanze no.

Nega entrambi i lati. La freccia R è la stessa, e la riga sotto, in rosso, è l'equivalenza negata: un "se e solo se" resta vero negando entrambi i lati, quindi x ∉ A ⇔ R(x) ∉ B. Le stringhe fuori da A sono quelle di Ā e quelle fuori da B sono quelle di B̄, quindi la riga dice x ∈ Ā ⇔ R(x) ∈ B̄. — 2. Nega entrambi i lati
La freccia $R$ è la stessa, e la riga sotto, in rosso, è l'equivalenza negata: un "se e solo se" resta vero negando entrambi i lati, quindi $x \notin A \iff R(x) \notin B$ . Le stringhe fuori da $A$ sono quelle di $\overline{A}$ e quelle fuori da $B$ sono quelle di $\overline{B}$ , quindi la riga dice $x \in \overline{A} \iff R(x) \in \overline{B}$ .

Mantieni il costo. Il riquadro in basso dice che la funzione è sempre la stessa R, quindi resta calcolabile in spazio O(log |x|). Con l'equivalenza negata, x ∉ A ⇔ R(x) ∉ B, R soddisfa la definizione di riduzione dal complemento di A al complemento di B. Il verso resta quello di partenza: da qui non si ottiene niente da B verso A. — 3. Mantieni il costo
Il riquadro in basso dice che la funzione è sempre la stessa $R$ , quindi resta calcolabile in spazio $O(\log |x|)$ . Con l'equivalenza negata, $x \notin A \iff R(x) \notin B$ , $R$ soddisfa la definizione di riduzione dal complemento di $A$ al complemento di $B$ . Il verso resta quello di partenza: da qui non si ottiene niente da $B$ verso $A$ .

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove: dispensa cap. 14, p. 53

proposizione

Proposizione B (complemento di un NP-completo)

chiesto in 5 domandedimostrato nel corso

Se $L$ è NP-completo, allora il suo complemento è coNP-completo (e viceversa).

Idea, frase per l'esame e dimostrazione +

Intuizione

Per la Proposizione A le stesse riduzioni funzionano sui complementi.

All'esame

Dà subito problemi coNP-completi: UNSAT, HAMILTON PATH COMPLEMENT, il complemento di TSP(D) e così via.

Da scrivere all'esame

Per la Proposizione B il complemento di un problema NP-completo è coNP-completo (per esempio UNSAT e HAMILTON PATH COMPLEMENT).

Dimostrazione illustrata

1 / 3

Prova l'appartenenza. Dal riquadro verde, B NP-completo, partono due frecce. Essere NP-completo vuol dire in particolare B ∈ NP, e allora il complemento B̄ sta in coNP per definizione. È la prima metà della coNP-completezza di B̄; resta da mostrare che ogni problema di coNP si riduce a lui. — 1. Prova l'appartenenza
Dal riquadro verde, $B$ NP-completo, partono due frecce. Essere NP-completo vuol dire in particolare $B \in \htmlData{term=NP}{\mathrm{NP}}$ , e allora il complemento $\overline{B}$ sta in coNP per definizione. È la prima metà della coNP-completezza di $\overline{B}$ ; resta da mostrare che ogni problema di coNP si riduce a lui.

Nega l'equivalenza. Negando i due lati di x ∈ L̄ ⇔ R(x) ∈ B si ottiene la riga in basso, x ∈ L ⇔ R(x) ∈ B̄: la stessa R riduce L a B̄, come dice la Proposizione A. L era un problema qualsiasi di coNP, quindi B̄ è coNP-hard, e con l'appartenenza vista all'inizio è coNP-completo. — 3. Nega l'equivalenza
Negando i due lati di $x \in \overline{L} \iff R(x) \in B$ si ottiene la riga in basso, $x \in L \iff R(x) \in \overline{B}$ : la stessa $R$ riduce $L$ a $\overline{B}$ , come dice la Proposizione A. $L$ era un problema qualsiasi di coNP, quindi $\overline{B}$ è coNP-hard, e con l'appartenenza vista all'inizio è coNP-completo.

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F12 n. 2 · F14 n. 2 · G20v2 n. 3 · LU22 n. 1 · ND n. 7

Classi

Dove: dispensa cap. 14, p. 54

proposizione

Proposizione C (chiusura dei complementi)

per l'oraledimostrato nel corso

Se una classe $C$ è chiusa rispetto alle riduzioni, anche $\mathrm{co}C$ lo è.

Idea, frase per l'esame e dimostrazione +

Intuizione

Si applica la chiusura di $C$ ai complementi, usando la Proposizione A.

All'esame

Per esempio coNP è chiusa rispetto alle riduzioni perché lo è NP.

Da scrivere all'esame

Per la Proposizione C, se una classe $\mathcal{C}$ è chiusa rispetto alle riduzioni lo è anche $\mathrm{co}\mathcal{C}$ (per esempio coNP, perché NP lo è).

Dimostrazione illustrata

1 / 3

Parti da un problema di coC. Per mostrare che coC è chiusa si prende B ∈ coC e un problema A che si riduce a B con R (riga in basso), e bisogna arrivare ad A ∈ coC. La freccia in alto è la definizione: B ∈ coC vuol dire che il complemento B̄ sta in C, e su C si può usare l'ipotesi di chiusura. — 1. Parti da un problema di co $C$
Per mostrare che $\mathrm{co}C$ è chiusa si prende $B \in \mathrm{co}C$ e un problema $A$ che si riduce a $B$ con $R$ (riga in basso), e bisogna arrivare ad $A \in \mathrm{co}C$ . La freccia in alto è la definizione: $B \in \mathrm{co}C$ vuol dire che il complemento $\overline{B}$ sta in $C$ , e su $C$ si può usare l'ipotesi di chiusura.

Scorri l'immagine o usa Avanti.

Dimostrazione

Classi

Dove: dispensa cap. 14, p. 54

proposizione

Proposizione D (un $C$ -completo in $\mathrm{co}C$ )

★ chiesto in 18 domandedimostrato nel corso

Se $C$ è chiusa rispetto alle riduzioni e un problema $C$ -completo sta in $\mathrm{co}C$ , allora $C = \mathrm{co}C$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

Tutto $C$ si riduce a quel problema, che sta in $\mathrm{co}C$ , chiusa per la Proposizione C: quindi $C \subseteq \mathrm{co}C$ , e per simmetria $\mathrm{co}C \subseteq C$ .

All'esame

Se un problema NP-completo stesse in coNP (o un coNP-completo in NP), allora $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}}$ .

Da scrivere all'esame

Per la Proposizione D, se un problema NP-completo stesse in coNP (o un coNP-completo in NP), allora $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}}$ .

Dimostrazione illustrata

1 / 3

Sfrutta il problema completo. Nel riquadro in alto c'è l'ipotesi: B è C-completo e sta anche in coC. Si suppone inoltre che C sia chiusa rispetto alle riduzioni. Sotto, A è un problema qualsiasi di C, e poiché B è C-completo si riduce a B con una riduzione R. — 1. Sfrutta il problema completo
Nel riquadro in alto c'è l'ipotesi: $B$ è $C$ -completo e sta anche in $\mathrm{co}C$ . Si suppone inoltre che $C$ sia chiusa rispetto alle riduzioni. Sotto, $A$ è un problema qualsiasi di $C$ , e poiché $B$ è $C$ -completo si riduce a $B$ con una riduzione $R$ .

Ottieni la prima inclusione. Per la Proposizione C anche coC è chiusa rispetto alle riduzioni. A si riduce a B, che sta in coC, quindi A ∈ coC: è la freccia che scende. A era un problema qualsiasi di C, perciò C ⊆ coC. Serve che B sia completo: un problema di C ∩ coC a cui non si riduce tutto C non porta a questa conclusione. — 2. Ottieni la prima inclusione
Per la Proposizione C anche $\mathrm{co}C$ è chiusa rispetto alle riduzioni. $A$ si riduce a $B$ , che sta in $\mathrm{co}C$ , quindi $A \in \mathrm{co}C$ : è la freccia che scende. $A$ era un problema qualsiasi di $C$ , perciò $C \subseteq \mathrm{co}C$ . Serve che $B$ sia completo: un problema di $C \cap \mathrm{co}C$ a cui non si riduce tutto $C$ non porta a questa conclusione.

Prendi i complementi. Per l'inclusione opposta si parte da A ∈ coC e si scende lungo la colonna. Per definizione Ā ∈ C; per la prima inclusione Ā ∈ coC; di nuovo per definizione il complemento di Ā, cioè A, sta in C. La freccia curva riassume i tre passi, coC ⊆ C, e con la prima inclusione si ha C = coC. — 3. Prendi i complementi
Per l'inclusione opposta si parte da $A \in \mathrm{co}C$ e si scende lungo la colonna. Per definizione $\overline{A} \in C$ ; per la prima inclusione $\overline{A} \in \mathrm{co}C$ ; di nuovo per definizione il complemento di $\overline{A}$ , cioè $A$ , sta in $C$ . La freccia curva riassume i tre passi, $\mathrm{co}C \subseteq C$ , e con la prima inclusione si ha $C = \mathrm{co}C$ .

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F02 n. 5 · F03 n. 1 · F03 n. 4 · F03 n. 7 · F04 n. 1 · F04 n. 7 · F07 n. 4 · F08 n. 3 · F12 n. 2 · F12 n. 5 · F14 n. 2 · F14 n. 7 · G20v1 n. 4 · G20v3 n. 1 · MZ22 n. 1 · LU22 n. 7 · LU24 n. 5 · ND n. 6

Classi

STRATEGIC COMPANIES · co-STRATEGIC COMPANIES

Dove: dispensa cap. 14, p. 54

proposizione

Se $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ allora $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}}$

per l'oraledimostrato nel corso

Se $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ , allora anche $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}}$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

P è chiusa per complemento: $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=P}{\mathrm{P}} = \mathrm{coP} = \htmlData{term=coNP}{\mathrm{coNP}}$ .

All'esame

Le risposte "solo se $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ " portano con sé anche $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}}$ ; il viceversa non è noto.

Da scrivere all'esame

Se $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ allora $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}}$ , perché P è chiusa per complemento: $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=P}{\mathrm{P}} = \mathrm{coP} = \htmlData{term=coNP}{\mathrm{coNP}}$ .

Dimostrazione illustrata

1 / 3

Assumi P = NP. Dentro l'ellisse vale l'ipotesi P = NP. Ogni problema di NP ha allora un decisore deterministico D che su input x risponde 0 o 1 in tempo polinomiale, poly(n). Il passo successivo usa due proprietà di D: è deterministico e si ferma sempre. — 1. Assumi $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$
Dentro l'ellisse vale l'ipotesi $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ . Ogni problema di NP ha allora un decisore deterministico $D$ che su input $x$ risponde $0$ o $1$ in tempo polinomiale, $\mathrm{poly}(n)$ . Il passo successivo usa due proprietà di $D$ : è deterministico e si ferma sempre.

Scambia le risposte. Da D si costruisce D', che fa gli stessi passi e alla fine risponde 1 - b invece di b: la tabella a destra scambia 0 e 1. D' decide il complemento nello stesso tempo, quindi il complemento di ogni problema di P sta in P, cioè coP = P. Con una macchina nondeterministica lo scambio non darebbe il complemento, perché accetterebbe quando almeno un ramo rifiuta. — 2. Scambia le risposte
Da $D$ si costruisce $D'$ , che fa gli stessi passi e alla fine risponde $1 - b$ invece di $b$ : la tabella a destra scambia $0$ e $1$ . $D'$ decide il complemento nello stesso tempo, quindi il complemento di ogni problema di P sta in P, cioè $\mathrm{coP} = \htmlData{term=P}{\mathrm{P}}$ . Con una macchina nondeterministica lo scambio non darebbe il complemento, perché accetterebbe quando almeno un ramo rifiuta.

Sostituisci la classe uguale. La catena si legge da destra: NP = P è l'ipotesi, P = coP viene dal passo precedente e coP = coNP segue dall'ipotesi, perché classi uguali hanno complementi uguali. Quindi NP = coNP. Il viceversa non è noto: da NP = coNP non si sa ricavare P = NP. — 3. Sostituisci la classe uguale
La catena si legge da destra: $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=P}{\mathrm{P}}$ è l'ipotesi, $\htmlData{term=P}{\mathrm{P}} = \mathrm{coP}$ viene dal passo precedente e $\mathrm{coP} = \htmlData{term=coNP}{\mathrm{coNP}}$ segue dall'ipotesi, perché classi uguali hanno complementi uguali. Quindi $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}}$ . Il viceversa non è noto: da $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}}$ non si sa ricavare $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ .

Scorri l'immagine o usa Avanti.

Dimostrazione

Classi

P NP coNP

Dove: dispensa cap. 14, p. 54; slide Lez. 4 (chiusura delle classi deterministiche per complemento)

proposizione

Proposizione $\htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=NP}{\mathrm{NP}} \cap \htmlData{term=coNP}{\mathrm{coNP}}$

chiesto in 6 domandedimostrato nel corso

$\htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=NP}{\mathrm{NP}} \cap \htmlData{term=coNP}{\mathrm{coNP}}$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

Se $L \in \htmlData{term=P}{\mathrm{P}}$ anche il suo complemento è in $\htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=NP}{\mathrm{NP}}$ , quindi $L \in \htmlData{term=coNP}{\mathrm{coNP}}$ ; e $L \in \htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=NP}{\mathrm{NP}}$ .

All'esame

Un problema in P ha sia certificati succinti sia squalifiche succinte; esistono problemi in $\htmlData{term=NP}{\mathrm{NP}} \cap \htmlData{term=coNP}{\mathrm{coNP}}$ non noti in P.

Da scrivere all'esame

$\htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=NP}{\mathrm{NP}} \cap \htmlData{term=coNP}{\mathrm{coNP}}$ : ogni problema in P sta in NP e, poiché P è chiusa per complemento, anche in coNP.

Dimostrazione illustrata

1 / 3

Usa il decisore come macchina NP. Il decisore deterministico D si legge come una macchina nondeterministica che a ogni passo ha una sola scelta. Sotto, la catena di stati q₀, q₁ è il suo unico ramo, che finisce con la stessa risposta 0/1 di D. La macchina accetta esattamente quando accetta D, in tempo polinomiale, quindi P ⊆ NP. — 1. Usa il decisore come macchina NP
Il decisore deterministico $D$ si legge come una macchina nondeterministica che a ogni passo ha una sola scelta. Sotto, la catena di stati $q_0, q_1$ è il suo unico ramo, che finisce con la stessa risposta $0/1$ di $D$ . La macchina accetta esattamente quando accetta $D$ , in tempo polinomiale, quindi $\htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=NP}{\mathrm{NP}}$ .

Decidi anche il complemento. Se D decide L ∈ P, la macchina D' fa gli stessi passi e risponde 1 - b (tabella a destra), quindi decide il complemento L̄ nello stesso tempo. Allora L̄ ∈ P ⊆ NP, e per definizione L ∈ coNP, da cui P ⊆ coNP. — 2. Decidi anche il complemento
Se $D$ decide $L \in \htmlData{term=P}{\mathrm{P}}$ , la macchina $D'$ fa gli stessi passi e risponde $1 - b$ (tabella a destra), quindi decide il complemento $\overline{L}$ nello stesso tempo. Allora $\overline{L} \in \htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=NP}{\mathrm{NP}}$ , e per definizione $L \in \htmlData{term=coNP}{\mathrm{coNP}}$ , da cui $\htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=coNP}{\mathrm{coNP}}$ .

Unisci le due inclusioni. Le due frecce partono da P: una arriva a NP, l'altra a coNP. Un problema che sta in entrambe le classi sta nella loro intersezione, quindi P ⊆ NP ∩ coNP. Non si sa se l'inclusione sia stretta, cioè se NP ∩ coNP contenga problemi fuori da P. — 3. Unisci le due inclusioni
Le due frecce partono da P: una arriva a NP, l'altra a coNP. Un problema che sta in entrambe le classi sta nella loro intersezione, quindi $\htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=NP}{\mathrm{NP}} \cap \htmlData{term=coNP}{\mathrm{coNP}}$ . Non si sa se l'inclusione sia stretta, cioè se $\htmlData{term=NP}{\mathrm{NP}} \cap \htmlData{term=coNP}{\mathrm{coNP}}$ contenga problemi fuori da P.

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F02 n. 4 · F03 n. 4 · F07 n. 4 · G20v2 n. 3 · MZ22 n. 1 · ND n. 7

Classi

P NP ∩ coNP

Dove: dispensa cap. 14, p. 55

Capitolo 15 · Problemi di ottimizzazione (DP)

proposizione

EXACT TSP è NP-hard (varianti di TSP)

per l'oraledimostrato nel corso

Le quattro varianti TSP(D), EXACT TSP, TSP COST e TSP si riducono ciascuna alla successiva; in particolare EXACT TSP è NP-hard. Lo si mostra riducendo HAMILTON CYCLE a EXACT TSP (il grafo ha un ciclo hamiltoniano se e solo se il giro ottimo costa esattamente $n$ ).

Idea, frase per l'esame e dimostrazione +

Intuizione

Chi sa trovare il giro ottimo sa anche dire quanto costa, e quindi se costa esattamente $B$ o al più $B$ .

All'esame

EXACT TSP non sembra stare né in NP né in coNP: è il problema che motiva la classe DP.

Da scrivere all'esame

EXACT TSP è NP-hard: con distanze 1 sugli archi e 2 altrove, $G$ ha un ciclo hamiltoniano se e solo se il giro ottimo costa esattamente $n$ .

Dimostrazione illustrata

1 / 4

Dal grafo alle città. A sinistra il grafo G, a destra l'istanza di EXACT TSP: una città per nodo e una distanza w(u, v) per ogni coppia. Le linee piene, gli archi di G, valgono 1; quelle tratteggiate in rosa, le coppie senza arco, valgono 2. Il valore 2 serve solo a rendere ogni coppia senza arco più cara di un arco. — 1. Dal grafo alle città
A sinistra il grafo $G$ , a destra l'istanza di EXACT TSP: una città per nodo e una distanza $w(u, v)$ per ogni coppia. Le linee piene, gli archi di $G$ , valgono $1$ ; quelle tratteggiate in rosa, le coppie senza arco, valgono $2$ . Il valore $2$ serve solo a rendere ogni coppia senza arco più cara di un arco.

Scorri l'immagine o usa Avanti.

Dimostrazione

Classi

NP DP

Problemi

TSP(D) · EXACT TSP · HAMILTON PATH

Dove: dispensa cap. 15, p. 58; slide Lez. 9

teorema

SAT-UNSAT è DP-completo

chiesto in 2 domandedimostrato nel corso

Date due formule $\varphi$ e $\varphi'$ in CNF con 3 letterali per clausola, decidere se $\varphi$ è soddisfacibile e $\varphi'$ no è DP-completo.

Idea, frase per l'esame e dimostrazione +

Intuizione

Sta in DP perché è l'intersezione di un problema NP ( $\varphi$ soddisfacibile) e di uno coNP ( $\varphi'$ insoddisfacibile); per la difficoltà, se $L = L_1 \cap L_2$ si usa $R(x) = (R_1(x), R_2(x))$ con le riduzioni a SAT.

All'esame

È il DP-completo di riferimento: per esempio SAT-UNSAT si riduce a $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_3$ perché $\htmlData{term=DP}{\mathrm{DP}} \subseteq \htmlData{term=Δ2}{\Delta_2^{\mathrm{P}}} \subseteq \htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}} \subseteq \htmlData{term=Σ3}{\Sigma_3^{\mathrm{P}}}$ .

Da scrivere all'esame

SAT-UNSAT è DP-completo e $\htmlData{term=DP}{\mathrm{DP}} \subseteq \htmlData{term=Δ2}{\Delta_2^{\mathrm{P}}} \subseteq \htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}} \cap \htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}$ : quindi si riduce a ogni problema $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ - o $\Pi_i^{\htmlData{term=P}{\mathrm{P}}}$ -completo con $i \ge 2$ (per esempio $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_3$ ).

Dimostrazione illustrata

1 / 4

Separa le due condizioni. Un'istanza è una coppia di formule (φ, ψ), e la risposta è sì quando φ è soddisfacibile e ψ no. Le due frecce separano le condizioni: la prima è un controllo NP, con certificato un assegnamento che soddisfa φ; la seconda è un controllo coNP. SAT-UNSAT è l'intersezione dei due linguaggi, quindi sta in DP. — 1. Separa le due condizioni
Un'istanza è una coppia di formule $(\varphi, \psi)$ , e la risposta è sì quando $\varphi$ è soddisfacibile e $\psi$ no. Le due frecce separano le condizioni: la prima è un controllo NP, con certificato un assegnamento che soddisfa $\varphi$ ; la seconda è un controllo coNP. SAT-UNSAT è l'intersezione dei due linguaggi, quindi sta in DP.

Controlla l'equivalenza. Mettendo insieme le due righe del passo prima, x ∈ A ∩ B se e solo se φ_x è soddisfacibile e ψ_x è insoddisfacibile, cioè se e solo se la coppia (φ_x, ψ_x) sta in SAT-UNSAT. La coppia si calcola eseguendo le due riduzioni una dopo l'altra, quindi è una riduzione da un problema qualsiasi di DP a SAT-UNSAT. Con l'appartenenza vista all'inizio, SAT-UNSAT è DP-completo. — 4. Controlla l'equivalenza
Mettendo insieme le due righe del passo prima, $x \in A \cap B$ se e solo se $\varphi_x$ è soddisfacibile e $\psi_x$ è insoddisfacibile, cioè se e solo se la coppia $(\varphi_x, \psi_x)$ sta in SAT-UNSAT. La coppia si calcola eseguendo le due riduzioni una dopo l'altra, quindi è una riduzione da un problema qualsiasi di DP a SAT-UNSAT. Con l'appartenenza vista all'inizio, SAT-UNSAT è DP-completo.

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F07 n. 2 · GE23 n. 5

Classi

DP

Problemi

SAT-UNSAT

Dove: dispensa cap. 15, p. 59; slide Lez. 9

Capitolo 16 · Macchine con oracolo

proposizione

Proposizione (oracoli NP-completi equivalenti)

per l'oraledimostrato nel corso

Per ogni linguaggio $L$ NP-completo, $\htmlData{term=P}{\mathrm{P}}^L = \htmlData{term=P}{\mathrm{P}}^{\htmlData{term=problem:SAT}{\mathrm{SAT}}}$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

Ogni domanda all'oracolo $L$ si traduce con una riduzione in una domanda a SAT, e viceversa, con costo polinomiale.

All'esame

Per questo si scrive $\htmlData{term=P}{\mathrm{P}}^{\htmlData{term=NP}{\mathrm{NP}}}$ , $\htmlData{term=NP}{\mathrm{NP}}^{\htmlData{term=NP}{\mathrm{NP}}}$ , $\htmlData{term=EXP}{\mathrm{EXP}}^{\htmlData{term=NP}{\mathrm{NP}}}$ invece di $\htmlData{term=P}{\mathrm{P}}^{\htmlData{term=problem:SAT}{\mathrm{SAT}}}$ , $\htmlData{term=NP}{\mathrm{NP}}^{\htmlData{term=problem:TSPD}{\mathrm{TSP(D)}}}$ , $\htmlData{term=EXP}{\mathrm{EXP}}^{\htmlData{term=problem:CLIQUE}{\mathrm{CLIQUE}}}$ .

Da scrivere all'esame

Per ogni $L$ NP-completo $\htmlData{term=P}{\mathrm{P}}^L = \htmlData{term=P}{\mathrm{P}}^{\htmlData{term=problem:SAT}{\mathrm{SAT}}} = \htmlData{term=P}{\mathrm{P}}^{\htmlData{term=NP}{\mathrm{NP}}}$ : le domande all'oracolo si traducono con una riduzione polinomiale, quindi conta solo la classe dell'oracolo.

Dimostrazione illustrata

1 / 3

Traduci le domande verso L. Per simulare una macchina con oracolo SAT usando l'oracolo L, ogni domanda "φ ∈ SAT?" passa per la riduzione polinomiale da SAT a L, che esiste perché L è NP-completo. Ne esce la stringa x da chiedere a L, con la stessa risposta: φ ∈ SAT ⇔ x ∈ L. Questo dà P^(SAT) ⊆ P^L. — 1. Traduci le domande verso $L$
Per simulare una macchina con oracolo SAT usando l'oracolo $L$ , ogni domanda " $\varphi \in \htmlData{term=problem:SAT}{\mathrm{SAT}}$ ?" passa per la riduzione polinomiale da SAT a $L$ , che esiste perché $L$ è NP-completo. Ne esce la stringa $x$ da chiedere a $L$ , con la stessa risposta: $\varphi \in \htmlData{term=problem:SAT}{\mathrm{SAT}} \iff x \in L$ . Questo dà $\htmlData{term=P}{\mathrm{P}}^{\htmlData{term=problem:SAT}{\mathrm{SAT}}} \subseteq \htmlData{term=P}{\mathrm{P}}^L$ .

Traduci le domande verso SAT. Il verso opposto usa l'altra metà della NP-completezza: L sta in NP, quindi la costruzione di Cook-Levin trasforma ogni domanda x in una formula φ_x con x ∈ L ⇔ φ_x ∈ SAT. Così una macchina con oracolo L si simula con l'oracolo SAT, e P^L ⊆ P^(SAT). — 2. Traduci le domande verso SAT
Il verso opposto usa l'altra metà della NP-completezza: $L$ sta in NP, quindi la costruzione di Cook-Levin trasforma ogni domanda $x$ in una formula $\varphi_x$ con $x \in L \iff \varphi_x \in \htmlData{term=problem:SAT}{\mathrm{SAT}}$ . Così una macchina con oracolo $L$ si simula con l'oracolo SAT, e $\htmlData{term=P}{\mathrm{P}}^L \subseteq \htmlData{term=P}{\mathrm{P}}^{\htmlData{term=problem:SAT}{\mathrm{SAT}}}$ .

Simula tutta la computazione. Le due macchine sono separate, ognuna con un solo oracolo. In alto la macchina con oracolo SAT passa ogni domanda φ per la riduzione verso L, e così P^(SAT) ⊆ P^L; in basso la macchina con oracolo L passa ogni domanda x per Cook-Levin verso SAT, e P^L ⊆ P^(SAT). Con al più p(n) domande lunghe al più p(n) e una riduzione da q(m) passi, il totale è al più p(n) + p(n) · q(p(n)), ancora un polinomio. Le due inclusioni danno P^L = P^(SAT). — 3. Simula tutta la computazione
Le due macchine sono separate, ognuna con un solo oracolo. In alto la macchina con oracolo SAT passa ogni domanda $\varphi$ per la riduzione verso $L$ , e così $\htmlData{term=P}{\mathrm{P}}^{\htmlData{term=problem:SAT}{\mathrm{SAT}}} \subseteq \htmlData{term=P}{\mathrm{P}}^L$ ; in basso la macchina con oracolo $L$ passa ogni domanda $x$ per Cook-Levin verso SAT, e $\htmlData{term=P}{\mathrm{P}}^L \subseteq \htmlData{term=P}{\mathrm{P}}^{\htmlData{term=problem:SAT}{\mathrm{SAT}}}$ . Con al più $p(n)$ domande lunghe al più $p(n)$ e una riduzione da $q(m)$ passi, il totale è al più $p(n) + p(n) \cdot q(p(n))$ , ancora un polinomio. Le due inclusioni danno $\htmlData{term=P}{\mathrm{P}}^L = \htmlData{term=P}{\mathrm{P}}^{\htmlData{term=problem:SAT}{\mathrm{SAT}}}$ .

Scorri l'immagine o usa Avanti.

Dimostrazione

Classi

Δ₂^P

Problemi

SAT

Dove: dispensa cap. 16, p. 63; slide Lez. 9

proposizione

Proposizione $C^D = C^{\mathrm{co}D}$

per l'oraledimostrato nel corso

Per ogni classe $C$ e ogni classe di oracoli $D$ : $C^D = C^{\mathrm{co}D}$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

Basta scambiare gli stati $q_{\mathrm{YES}}$ e $q_{\mathrm{NO}}$ : l'oracolo è una scatola nera che risponde in un passo.

All'esame

Per questo non si scrivono $\htmlData{term=P}{\mathrm{P}}^{\htmlData{term=coNP}{\mathrm{coNP}}}$ o $\htmlData{term=NP}{\mathrm{NP}}^{\htmlData{term=coNP}{\mathrm{coNP}}}$ : per esempio $\htmlData{term=NP}{\mathrm{NP}}^{\htmlData{term=coNP}{\mathrm{coNP}}} = \htmlData{term=NP}{\mathrm{NP}}^{\htmlData{term=NP}{\mathrm{NP}}} = \htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ .

Da scrivere all'esame

$\mathcal{C}^{\mathcal{D}} = \mathcal{C}^{\mathrm{co}\mathcal{D}}$ (basta scambiare $q_{\mathrm{YES}}$ e $q_{\mathrm{NO}}$ ): per esempio $\htmlData{term=NP}{\mathrm{NP}}^{\htmlData{term=coNP}{\mathrm{coNP}}} = \htmlData{term=NP}{\mathrm{NP}}^{\htmlData{term=NP}{\mathrm{NP}}} = \htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ .

Dimostrazione illustrata

1 / 3

Cambia soltanto l'oracolo. A sinistra la macchina M^D manda la domanda x all'oracolo D e riceve yes o no. A destra c'è la stessa situazione con l'oracolo complementare D̄. L'oracolo è una scatola nera: la macchina scrive x e al passo dopo si trova nello stato q_(YES) o q_(NO). — 1. Cambia soltanto l'oracolo
A sinistra la macchina $M^D$ manda la domanda $x$ all'oracolo $D$ e riceve yes o no. A destra c'è la stessa situazione con l'oracolo complementare $\overline{D}$ . L'oracolo è una scatola nera: la macchina scrive $x$ e al passo dopo si trova nello stato $q_{\mathrm{YES}}$ o $q_{\mathrm{NO}}$ .

Inverti ogni risposta. Sulla stessa domanda x, se D risponde b allora D̄ risponde 1 - b. La macchina con oracolo D̄ inverte la risposta (riquadro rosa) e torna a b: basta scambiare q_(YES) e q_(NO) nella sua tabella di transizione. Da lì fa le stesse mosse della macchina originale, con gli stessi passi e le stesse celle, quindi resta nel budget di C. — 2. Inverti ogni risposta
Sulla stessa domanda $x$ , se $D$ risponde $b$ allora $\overline{D}$ risponde $1 - b$ . La macchina con oracolo $\overline{D}$ inverte la risposta (riquadro rosa) e torna a $b$ : basta scambiare $q_{\mathrm{YES}}$ e $q_{\mathrm{NO}}$ nella sua tabella di transizione. Da lì fa le stesse mosse della macchina originale, con gli stessi passi e le stesse celle, quindi resta nel budget di $C$ .

Ripeti nei due versi. La freccia verso destra è l'inclusione appena vista, C^D ⊆ C^(D̄). Quella verso sinistra è lo stesso scambio partendo da D̄, il cui complemento è D. Vale per ogni singolo oracolo, quindi anche per una classe di oracoli: C^D = C^(coD), e per esempio NP^(coNP) = NP^(NP). — 3. Ripeti nei due versi
La freccia verso destra è l'inclusione appena vista, $C^D \subseteq C^{\overline{D}}$ . Quella verso sinistra è lo stesso scambio partendo da $\overline{D}$ , il cui complemento è $D$ . Vale per ogni singolo oracolo, quindi anche per una classe di oracoli: $C^D = C^{\mathrm{co}D}$ , e per esempio $\htmlData{term=NP}{\mathrm{NP}}^{\htmlData{term=coNP}{\mathrm{coNP}}} = \htmlData{term=NP}{\mathrm{NP}}^{\htmlData{term=NP}{\mathrm{NP}}}$ .

Scorri l'immagine o usa Avanti.

Dimostrazione

Classi

Δ₂^P Σ₂^P

Dove: dispensa cap. 16, p. 63; slide Lez. 9

proposizione

Oracoli inutili e $\htmlData{term=DP}{\mathrm{DP}} \subseteq \htmlData{term=P}{\mathrm{P}}^{\htmlData{term=NP}{\mathrm{NP}}}$

★ chiesto in 10 domandedimostrato nel corso

$\htmlData{term=P}{\mathrm{P}}^{\htmlData{term=P}{\mathrm{P}}} = \htmlData{term=P}{\mathrm{P}}$ e $\htmlData{term=NP}{\mathrm{NP}}^{\htmlData{term=P}{\mathrm{P}}} = \htmlData{term=NP}{\mathrm{NP}}$ ; inoltre $\htmlData{term=DP}{\mathrm{DP}} \subseteq \htmlData{term=P}{\mathrm{P}}^{\htmlData{term=NP}{\mathrm{NP}}}$ . Non si sa se $\htmlData{term=NP}{\mathrm{NP}}^{\htmlData{term=NP}{\mathrm{NP}}} = \htmlData{term=NP}{\mathrm{NP}}$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

Un oracolo in P si esegue "in linea" con costo polinomiale; una domanda NP e una coNP si risolvono con due chiamate a un oracolo NP.

All'esame

Colloca DP dentro $\htmlData{term=Δ2}{\Delta_2^{\mathrm{P}}} = \htmlData{term=P}{\mathrm{P}}^{\htmlData{term=NP}{\mathrm{NP}}}$ , per esempio per le riduzioni da SAT-UNSAT verso i livelli più alti di PH.

Da scrivere all'esame

$\htmlData{term=P}{\mathrm{P}}^{\htmlData{term=P}{\mathrm{P}}} = \htmlData{term=P}{\mathrm{P}}$ e $\htmlData{term=NP}{\mathrm{NP}}^{\htmlData{term=P}{\mathrm{P}}} = \htmlData{term=NP}{\mathrm{NP}}$ (oracolo eseguito in linea); $\htmlData{term=DP}{\mathrm{DP}} \subseteq \htmlData{term=P}{\mathrm{P}}^{\htmlData{term=NP}{\mathrm{NP}}} = \htmlData{term=Δ2}{\Delta_2^{\mathrm{P}}} \subseteq \htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}} \cap \htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}$ , perché bastano due domande a un oracolo NP.

Dimostrazione illustrata

1 / 4

Sostituisci l'oracolo polinomiale. A sinistra M^A manda la domanda x all'oracolo A, che sta in P. A destra M' non ha oracolo: esegue da sé il decisore polinomiale di A su x, come sottoprogramma, e prosegue con la risposta. Le domande sono al più p(n), lunghe al più p(n), e se il decisore costa q(m) il totale resta polinomiale, p(n) + p(n) · q(p(n)). — 1. Sostituisci l'oracolo polinomiale
A sinistra $M^A$ manda la domanda $x$ all'oracolo $A$ , che sta in P. A destra $M'$ non ha oracolo: esegue da sé il decisore polinomiale di $A$ su $x$ , come sottoprogramma, e prosegue con la risposta. Le domande sono al più $p(n)$ , lunghe al più $p(n)$ , e se il decisore costa $q(m)$ il totale resta polinomiale, $p(n) + p(n) \cdot q(p(n))$ .

Mantieni le scelte della macchina. Le due colonne applicano la stessa simulazione a una macchina P e a una macchina NP con oracolo in P. Il sottoprogramma che sostituisce l'oracolo è deterministico, quindi su ogni ramo della macchina NP dà la risposta giusta e il ramo resta polinomiale. Ne vengono Pᴾ = P e NPᴾ = NP. Con un oracolo NP non si sa fare lo stesso: per una risposta no bisognerebbe escludere tutti i certificati. — 2. Mantieni le scelte della macchina
Le due colonne applicano la stessa simulazione a una macchina P e a una macchina NP con oracolo in P. Il sottoprogramma che sostituisce l'oracolo è deterministico, quindi su ogni ramo della macchina NP dà la risposta giusta e il ramo resta polinomiale. Ne vengono $\htmlData{term=P}{\mathrm{P}}^{\htmlData{term=P}{\mathrm{P}}} = \htmlData{term=P}{\mathrm{P}}$ e $\htmlData{term=NP}{\mathrm{NP}}^{\htmlData{term=P}{\mathrm{P}}} = \htmlData{term=NP}{\mathrm{NP}}$ . Con un oracolo NP non si sa fare lo stesso: per una risposta no bisognerebbe escludere tutti i certificati.

Estendi a tutta DP. Ogni L ∈ DP si riduce a SAT-UNSAT, che è DP-completo, e SAT-UNSAT sta in P^(NP). P^(NP) è chiusa rispetto alle riduzioni: la macchina calcola prima R(x), con R la riduzione, e poi decide SAT-UNSAT su R(x). Quindi L ∈ P^(NP) e DP ⊆ P^(NP). — 4. Estendi a tutta DP
Ogni $L \in \htmlData{term=DP}{\mathrm{DP}}$ si riduce a SAT-UNSAT, che è DP-completo, e SAT-UNSAT sta in $\htmlData{term=P}{\mathrm{P}}^{\htmlData{term=NP}{\mathrm{NP}}}$ . $\htmlData{term=P}{\mathrm{P}}^{\htmlData{term=NP}{\mathrm{NP}}}$ è chiusa rispetto alle riduzioni: la macchina calcola prima $R(x)$ , con $R$ la riduzione, e poi decide SAT-UNSAT su $R(x)$ . Quindi $L \in \htmlData{term=P}{\mathrm{P}}^{\htmlData{term=NP}{\mathrm{NP}}}$ e $\htmlData{term=DP}{\mathrm{DP}} \subseteq \htmlData{term=P}{\mathrm{P}}^{\htmlData{term=NP}{\mathrm{NP}}}$ .

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F07 n. 2 · G16 n. 3 · G20v1 n. 3 · G20v2 n. 2 · G20v3 n. 1 · G20v5 n. 1 · G20v5 n. 3 · MZ22 n. 2 · GE23 n. 7 · MA23 n. 6

Classi

P NP DP Δ₂^P

Dove: dispensa cap. 16, p. 63; slide Lez. 9

Capitolo 17 · Gerarchia polinomiale

teorema

Teorema 17.8 (certificati per $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ )

per l'oraledimostrato nel corso

Per ogni $i \ge 1$ , $L \in \Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ se e solo se esiste una relazione $R$ polinomialmente bilanciata, con $\{x;y : (x, y) \in R\}$ in $\Pi_{i-1}^{\htmlData{term=P}{\mathrm{P}}}$ , tale che $L = \{x : \text{esiste } y \text{ con } (x, y) \in R\}$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

Ogni livello aggiunge un "esiste" davanti a un controllo del livello di sotto; per $i = 1$ è la Proposizione 9.1 su NP.

All'esame

È la base della prova del collasso (Teorema 17.9) e dell'appartenenza di $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_i$ a $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ .

Da scrivere all'esame

Per il Teorema 17.8, $L \in \Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ sse $L = \{x : \exists y\ (x, y) \in R\}$ con $R$ polinomialmente bilanciata e verificabile in $\Pi_{i-1}^{\htmlData{term=P}{\mathrm{P}}}$ .

Dimostrazione illustrata

1 / 4

Leggi la caratterizzazione. L sta in Σᵢᴾ se e solo se x ∈ L equivale a "esiste y con |y| ≤ p(|x|) e R(x, y)", con il controllo R in Πᵢ₋₁ᴾ. Nel disegno y è il riquadro tratteggiato fra x e R, e la graffa sotto ne limita la lunghezza. Per i = 1 il controllo sta in Π₀ᴾ = P e si ritrova la caratterizzazione di NP con i certificati. — 1. Leggi la caratterizzazione
$L$ sta in $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ se e solo se $x \in L$ equivale a "esiste $y$ con $|y| \le p(|x|)$ e $R(x, y)$ ", con il controllo $R$ in $\Pi_{i-1}^{\htmlData{term=P}{\mathrm{P}}}$ . Nel disegno $y$ è il riquadro tratteggiato fra $x$ e $R$ , e la graffa sotto ne limita la lunghezza. Per $i = 1$ il controllo sta in $\Pi_0^{\mathrm{P}} = \htmlData{term=P}{\mathrm{P}}$ e si ritrova la caratterizzazione di NP con i certificati.

Dal certificato alla macchina. La macchina M riceve x e indovina y (freccia guess). Poi chiede all'oracolo, che sta in Σᵢ₋₁ᴾ, se (x, y) sta nel complemento di R, e inverte la risposta (freccia invert): accetta se l'oracolo dice no, cioè se vale R(x, y). È una macchina NP con oracolo in Σᵢ₋₁ᴾ, quindi L ∈ Σᵢᴾ. — 2. Dal certificato alla macchina
La macchina $M$ riceve $x$ e indovina $y$ (freccia guess). Poi chiede all'oracolo, che sta in $\Sigma_{i-1}^{\htmlData{term=P}{\mathrm{P}}}$ , se $(x, y)$ sta nel complemento di $R$ , e inverte la risposta (freccia invert): accetta se l'oracolo dice no, cioè se vale $R(x, y)$ . È una macchina NP con oracolo in $\Sigma_{i-1}^{\htmlData{term=P}{\mathrm{P}}}$ , quindi $L \in \Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ .

Dalla macchina al certificato. Nel verso opposto L è decisa da una macchina NP con oracolo K ∈ Σᵢ₋₁ᴾ. Il certificato y registra un ramo accettante, quello verde: le scelte fatte, le risposte a₁, …, a_k date dall'oracolo alle domande Q lungo il ramo e, per ogni risposta sì del ramo, un testimone fra w₁, …, w_m. Tutto ha lunghezza polinomiale; per le risposte no il certificato non contiene niente. — 3. Dalla macchina al certificato
Nel verso opposto $L$ è decisa da una macchina NP con oracolo $K \in \Sigma_{i-1}^{\htmlData{term=P}{\mathrm{P}}}$ . Il certificato $y$ registra un ramo accettante, quello verde: le scelte fatte, le risposte $a_1, \dots, a_k$ date dall'oracolo alle domande $Q$ lungo il ramo e, per ogni risposta sì del ramo, un testimone fra $w_1, \dots, w_m$ . Tutto ha lunghezza polinomiale; per le risposte no il certificato non contiene niente.

Verifica anche le risposte negative. Il controllo verify(x, y) simula il ramo scritto in y e verifica le risposte. Per le risposte sì controlla i testimoni, per le risposte no fa un controllo universale, che la domanda non stia in K; entrambi stanno in Πᵢ₋₁ᴾ, quindi anche la loro congiunzione, e R ∈ Πᵢ₋₁ᴾ. Per i = 1 l'oracolo sta in P e R è un controllo in tempo polinomiale. — 4. Verifica anche le risposte negative
Il controllo $\mathrm{verify}(x, y)$ simula il ramo scritto in $y$ e verifica le risposte. Per le risposte sì controlla i testimoni, per le risposte no fa un controllo universale, che la domanda non stia in $K$ ; entrambi stanno in $\Pi_{i-1}^{\htmlData{term=P}{\mathrm{P}}}$ , quindi anche la loro congiunzione, e $R \in \Pi_{i-1}^{\htmlData{term=P}{\mathrm{P}}}$ . Per $i = 1$ l'oracolo sta in P e $R$ è un controllo in tempo polinomiale.

Scorri l'immagine o usa Avanti.

Dimostrazione

Classi

Σ_i^P Π_i^P

Dove: dispensa cap. 17, p. 64; slide Lez. 9. La dispensa omette la prova; le slide la danno per induzione su $i$ .

corollario

Corollario 1 del Teorema 17.8 (certificati per $\Pi_i^{\htmlData{term=P}{\mathrm{P}}}$ )

per l'oraledimostrato nel corso

Per ogni $i \ge 1$ , $L \in \Pi_i^{\htmlData{term=P}{\mathrm{P}}}$ se e solo se esiste una relazione $R$ polinomialmente bilanciata, con $\{x;y : (x, y) \in R\}$ in $\Sigma_{i-1}^{\htmlData{term=P}{\mathrm{P}}}$ , tale che $L = \{x : \text{per ogni } y \text{ con } |y| \le |x|^k,\ (x, y) \in R\}$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

$\Pi_i^{\htmlData{term=P}{\mathrm{P}}} = \mathrm{co}\Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ : complementando, "esiste" diventa "per ogni".

Da scrivere all'esame

Per il Corollario 1 del Teorema 17.8, $L \in \Pi_i^{\htmlData{term=P}{\mathrm{P}}}$ sse $L = \{x : \forall y\ (x, y) \in R\}$ con $R$ polinomialmente bilanciata e verificabile in $\Sigma_{i-1}^{\htmlData{term=P}{\mathrm{P}}}$ .

Dimostrazione illustrata

1 / 3

Parti dal complemento. Πᵢᴾ è la classe dei complementi dei linguaggi di Σᵢᴾ. Nel disegno L̄ sta dentro Σᵢᴾ, e questo basta per dire L ∈ Πᵢᴾ. La prova applica il Teorema 17.8 a L̄ e poi nega la frase che ottiene. — 1. Parti dal complemento
$\Pi_i^{\htmlData{term=P}{\mathrm{P}}}$ è la classe dei complementi dei linguaggi di $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ . Nel disegno $\overline{L}$ sta dentro $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ , e questo basta per dire $L \in \Pi_i^{\htmlData{term=P}{\mathrm{P}}}$ . La prova applica il Teorema 17.8 a $\overline{L}$ e poi nega la frase che ottiene.

Caratterizza il complemento. Per il Teorema 17.8, x ∈ L̄ se e solo se esiste y con |y| ≤ p(|x|) e R(x, y), dove il controllo R, sotto la graffa, sta in Πᵢ₋₁ᴾ. Il limite su |y| entra nella parentesi con un ∧: davanti a "esiste" non cambia niente, perché R è bilanciata e non contiene coppie con y lungo. — 2. Caratterizza il complemento
Per il Teorema 17.8, $x \in \overline{L}$ se e solo se esiste $y$ con $|y| \le p(|x|)$ e $R(x, y)$ , dove il controllo $R$ , sotto la graffa, sta in $\Pi_{i-1}^{\htmlData{term=P}{\mathrm{P}}}$ . Il limite su $|y|$ entra nella parentesi con un $\land$ : davanti a "esiste" non cambia niente, perché $R$ è bilanciata e non contiene coppie con $y$ lungo.

Nega tutta la frase. x ∈ L vuol dire x ∉ L̄, cioè che non esiste un y corto con R(x, y). Portando la negazione dentro, "non esiste" diventa "per ogni": per ogni y con |y| ≤ p(|x|) vale ¬ R(x, y). Il complemento di un controllo in Πᵢ₋₁ᴾ sta in Σᵢ₋₁ᴾ, come indica la graffa. Il limite su |y| resta come premessa dell'implicazione: il "per ogni" riguarda solo i y corti. — 3. Nega tutta la frase
$x \in L$ vuol dire $x \notin \overline{L}$ , cioè che non esiste un $y$ corto con $R(x, y)$ . Portando la negazione dentro, "non esiste" diventa "per ogni": per ogni $y$ con $|y| \le p(|x|)$ vale $\neg R(x, y)$ . Il complemento di un controllo in $\Pi_{i-1}^{\htmlData{term=P}{\mathrm{P}}}$ sta in $\Sigma_{i-1}^{\htmlData{term=P}{\mathrm{P}}}$ , come indica la graffa. Il limite su $|y|$ resta come premessa dell'implicazione: il "per ogni" riguarda solo i $y$ corti.

Scorri l'immagine o usa Avanti.

Dimostrazione

Classi

Σ_i^P Π_i^P

Dove: dispensa cap. 17, p. 64; slide Lez. 9

corollario

Corollario 2 del Teorema 17.8 (forma con i quantificatori)

chiesto in 1 domandadimostrato nel corso

Per ogni $i \ge 1$ , $L \in \Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ se e solo se esiste una relazione $R$ polinomialmente bilanciata e decidibile in tempo polinomiale tale che $L = \{x : \exists y_1 \forall y_2 \exists y_3 \ldots Q y_i \text{ con } (x, y_1, \ldots, y_i) \in R\}$ , dove $Q$ è $\exists$ se $i$ è dispari e $\forall$ se $i$ è pari.

Idea, frase per l'esame e dimostrazione +

Intuizione

Il livello di un problema nella gerarchia è il numero di alternanze di quantificatori davanti a un controllo polinomiale.

All'esame

Si usa per collocare un problema in $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ contando i quantificatori, e per mostrare che $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_i \in \Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ .

Da scrivere all'esame

Per il Corollario 2 del Teorema 17.8, $L \in \Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ sse $L = \{x : \exists y_1\, \forall y_2 \dots Q y_i\ R(x, y_1, \dots, y_i)\}$ con $R$ polinomiale: il livello è il numero di alternanze.

Dimostrazione illustrata

1 / 4

Parti dal primo certificato. Per il Teorema 17.8, L ∈ Σᵢᴾ se e solo se esiste un certificato y con |y| ≤ p(|x|) tale che la coppia (x, y) supera un controllo R₁ di Πᵢ₋₁ᴾ. Nel riquadro verde c'è questo ∃ y; in quello viola il controllo che resta, un livello più in basso. — 1. Parti dal primo certificato
Per il Teorema 17.8, $L \in \Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ se e solo se esiste un certificato $y$ con $|y| \le p(|x|)$ tale che la coppia $(x, y)$ supera un controllo $R_1$ di $\Pi_{i-1}^{\htmlData{term=P}{\mathrm{P}}}$ . Nel riquadro verde c'è questo $\exists y$ ; in quello viola il controllo che resta, un livello più in basso.

Espandi il livello successivo. Il controllo R₁ sta in Πᵢ₋₁ᴾ, e il Corollario 1 lo scrive a sua volta come un blocco ∀ z, ora in viola, davanti a un controllo R₂(x, y, z) di Σᵢ₋₂ᴾ, con z anch'esso di lunghezza polinomiale. A ogni espansione il quantificatore davanti cambia e il controllo che resta scende di un livello. — 2. Espandi il livello successivo
Il controllo $R_1$ sta in $\Pi_{i-1}^{\htmlData{term=P}{\mathrm{P}}}$ , e il Corollario 1 lo scrive a sua volta come un blocco $\forall z$ , ora in viola, davanti a un controllo $R_2(x, y, z)$ di $\Sigma_{i-2}^{\htmlData{term=P}{\mathrm{P}}}$ , con $z$ anch'esso di lunghezza polinomiale. A ogni espansione il quantificatore davanti cambia e il controllo che resta scende di un livello.

Arriva a un controllo polinomiale. Dopo i espansioni la fila ha i blocchi alternati, ∃ y₁ ∀ y₂ … Qᵢ yᵢ, e il riquadro grigio in fondo è un controllo R in P, perché al livello 0 si ha Σ₀ᴾ = Π₀ᴾ = P. L'ultimo quantificatore Qᵢ è ∃ se i è dispari e ∀ se è pari. Ogni y_j resta polinomiale in |x|, perché un polinomio di un polinomio è ancora un polinomio. — 3. Arriva a un controllo polinomiale
Dopo $i$ espansioni la fila ha $i$ blocchi alternati, $\exists y_1\, \forall y_2 \ldots Q_i y_i$ , e il riquadro grigio in fondo è un controllo $R$ in $\htmlData{term=P}{\mathrm{P}}$ , perché al livello 0 si ha $\Sigma_0^{\mathrm{P}} = \Pi_0^{\mathrm{P}} = \htmlData{term=P}{\mathrm{P}}$ . L'ultimo quantificatore $Q_i$ è $\exists$ se $i$ è dispari e $\forall$ se è pari. Ogni $y_j$ resta polinomiale in $|x|$ , perché un polinomio di un polinomio è ancora un polinomio.

Leggi anche il verso inverso. Le due righe sono le due forme del corollario: se il primo blocco è ∃ il linguaggio sta in Σᵢᴾ, se è ∀ sta in Πᵢᴾ, e ogni blocco vale un livello. Il verso inverso rifà i passi al contrario. Tolto ∃ y₁ resta una forma di i-1 blocchi aperta da ∀, che per induzione sta in Πᵢ₋₁ᴾ, e il Teorema 17.8 mette L in Σᵢᴾ. — 4. Leggi anche il verso inverso
Le due righe sono le due forme del corollario: se il primo blocco è $\exists$ il linguaggio sta in $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ , se è $\forall$ sta in $\Pi_i^{\htmlData{term=P}{\mathrm{P}}}$ , e ogni blocco vale un livello. Il verso inverso rifà i passi al contrario. Tolto $\exists y_1$ resta una forma di $i-1$ blocchi aperta da $\forall$ , che per induzione sta in $\Pi_{i-1}^{\htmlData{term=P}{\mathrm{P}}}$ , e il Teorema 17.8 mette $L$ in $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ .

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

G20v3 n. 2

Classi

Σ_i^P Π_i^P PH

Dove: dispensa cap. 17, p. 65; slide Lez. 9

teorema

Teorema 17.9 (collasso di PH)

★ chiesto in 23 domandedimostrato nel corso

Se per qualche $i \ge 1$ vale $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}} = \Pi_i^{\htmlData{term=P}{\mathrm{P}}}$ , allora per ogni $j \gt i$ : $\Sigma_j^{\htmlData{term=P}{\mathrm{P}}} = \Pi_j^{\htmlData{term=P}{\mathrm{P}}} = \Delta_j^{\htmlData{term=P}{\mathrm{P}}} = \Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ , cioè la gerarchia polinomiale collassa al livello $i$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

Basta mostrare $\Sigma_{i+1}^{\htmlData{term=P}{\mathrm{P}}} = \Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ : due "esiste" consecutivi si fondono in uno solo, poi si ripete salendo.

All'esame

È lo strumento delle risposte "solo se PH collassa": per esempio una riduzione da $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_i$ al suo complemento esiste solo se PH collassa al livello $i$ .

Da scrivere all'esame

Per il Teorema 17.9, se $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}} = \Pi_i^{\htmlData{term=P}{\mathrm{P}}}$ allora PH collassa al livello $i$ : per esempio una riduzione da $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_i$ al suo complemento esiste solo se PH collassa al livello $i$ .

Dimostrazione illustrata

1 / 5

Assumi l'uguaglianza al livello i. Il riquadro rosa è l'ipotesi del teorema: per un certo i ≥ 1, Σᵢᴾ = Πᵢᴾ. Non si sa se valga per qualche i, per questo il risultato è condizionale: dice che cosa succede a tutta la gerarchia sopra il livello i se l'uguaglianza vale. — 1. Assumi l'uguaglianza al livello $i$
Il riquadro rosa è l'ipotesi del teorema: per un certo $i \ge 1$ , $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}} = \Pi_i^{\htmlData{term=P}{\mathrm{P}}}$ . Non si sa se valga per qualche $i$ , per questo il risultato è condizionale: dice che cosa succede a tutta la gerarchia sopra il livello $i$ se l'uguaglianza vale.

Riscrivi il controllo interno. Per il Teorema 17.8 un linguaggio L di Σᵢ₊₁ᴾ è un ∃ y davanti a un controllo R(x, y) di Πᵢᴾ, come nella riga in alto. Per l'ipotesi lo stesso controllo sta anche in Σᵢᴾ, e la riga sotto lo riscrive con questa etichetta. Così dopo ∃ y viene un controllo che comincia anche lui con un "esiste". — 2. Riscrivi il controllo interno
Per il Teorema 17.8 un linguaggio $L$ di $\Sigma_{i+1}^{\htmlData{term=P}{\mathrm{P}}}$ è un $\exists y$ davanti a un controllo $R(x, y)$ di $\Pi_i^{\htmlData{term=P}{\mathrm{P}}}$ , come nella riga in alto. Per l'ipotesi lo stesso controllo sta anche in $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ , e la riga sotto lo riscrive con questa etichetta. Così dopo $\exists y$ viene un controllo che comincia anche lui con un "esiste".

Fondi due scelte esistenziali. Il Teorema 17.8, applicato al controllo nel riquadro, gli mette davanti un secondo ∃ z e lascia un controllo di Πᵢ₋₁ᴾ. I due "esiste" di fila si fondono in uno sulla coppia (y, z), ancora polinomiale in |x|, e si ottiene la forma di Σᵢᴾ. Con Σᵢᴾ ⊆ Σᵢ₊₁ᴾ, che vale sempre, si arriva all'uguaglianza scritta in fondo. — 3. Fondi due scelte esistenziali
Il Teorema 17.8, applicato al controllo nel riquadro, gli mette davanti un secondo $\exists z$ e lascia un controllo di $\Pi_{i-1}^{\htmlData{term=P}{\mathrm{P}}}$ . I due "esiste" di fila si fondono in uno sulla coppia $(y, z)$ , ancora polinomiale in $|x|$ , e si ottiene la forma di $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ . Con $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}} \subseteq \Sigma_{i+1}^{\htmlData{term=P}{\mathrm{P}}}$ , che vale sempre, si arriva all'uguaglianza scritta in fondo.

Chiudi per complemento. La barra sopra Σᵢᴾ indica la classe dei complementi, che per definizione è Πᵢᴾ: l'ipotesi dice che Σᵢᴾ è chiusa per complemento. Da qui segue anche la classe universale del livello sopra: Πᵢ₊₁ᴾ = coΣᵢ₊₁ᴾ = coΣᵢᴾ = Πᵢᴾ = Σᵢᴾ. — 4. Chiudi per complemento
La barra sopra $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ indica la classe dei complementi, che per definizione è $\Pi_i^{\htmlData{term=P}{\mathrm{P}}}$ : l'ipotesi dice che $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ è chiusa per complemento. Da qui segue anche la classe universale del livello sopra: $\Pi_{i+1}^{\htmlData{term=P}{\mathrm{P}}} = \mathrm{co}\Sigma_{i+1}^{\htmlData{term=P}{\mathrm{P}}} = \mathrm{co}\Sigma_i^{\htmlData{term=P}{\mathrm{P}}} = \Pi_i^{\htmlData{term=P}{\mathrm{P}}} = \Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ .

Ripeti verso l'alto. Ora vale Σᵢ₊₁ᴾ = Πᵢ₊₁ᴾ, cioè l'ipotesi un livello più su, e lo stesso argomento dà Σᵢ₊₂ᴾ = Πᵢ₊₂ᴾ. Ogni freccia della catena è un passo dell'induzione e ogni livello raggiunto è uguale a Σᵢᴾ, da cui PH = Σᵢᴾ. Il collasso va solo verso l'alto: sui livelli sotto i l'ipotesi non dice niente. — 5. Ripeti verso l'alto
Ora vale $\Sigma_{i+1}^{\htmlData{term=P}{\mathrm{P}}} = \Pi_{i+1}^{\htmlData{term=P}{\mathrm{P}}}$ , cioè l'ipotesi un livello più su, e lo stesso argomento dà $\Sigma_{i+2}^{\htmlData{term=P}{\mathrm{P}}} = \Pi_{i+2}^{\htmlData{term=P}{\mathrm{P}}}$ . Ogni freccia della catena è un passo dell'induzione e ogni livello raggiunto è uguale a $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ , da cui $\htmlData{term=PH}{\mathrm{PH}} = \Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ . Il collasso va solo verso l'alto: sui livelli sotto $i$ l'ipotesi non dice niente.

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F03 n. 1 · F03 n. 7 · F04 n. 1 · F04 n. 7 · F06 n. 2 · F07 n. 4 · F07 n. 7 · F08 n. 3 · F12 n. 2 · F12 n. 5 · F13 n. 1 · L18 n. 1 · L18 n. 7 · G20v1 n. 1 · G20v1 n. 4 · G20v3 n. 1 · G20v5 n. 1 · MZ22 n. 2 · LU22 n. 7 · FE23 n. 7 · MA23 n. 2 · E26 n. 5 · ND n. 6

Classi

Σ_i^P Π_i^P PH

Dove: dispensa cap. 17, p. 65; slide Lez. 9

corollario

Corollario (collasso al primo livello)

★ chiesto in 10 domandedimostrato nel corso

Se $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ , o anche solo $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}}$ , la gerarchia polinomiale collassa al primo livello.

Idea, frase per l'esame e dimostrazione +

Intuizione

È il Teorema 17.9 con $i = 1$ .

All'esame

Senza una prova di $\htmlData{term=P}{\mathrm{P}} \neq \htmlData{term=NP}{\mathrm{NP}}$ non si può dimostrare che PH sia davvero una gerarchia; serve per le risposte "solo se $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}}$ ".

Da scrivere all'esame

Se $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}}$ (in particolare se $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ ) allora, per il Teorema 17.9 con $i = 1$ , PH collassa al primo livello: $\htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=NP}{\mathrm{NP}}$ .

Dimostrazione illustrata

1 / 3

Usa l'ipotesi NP = coNP. Le due etichette in basso traducono l'ipotesi nel linguaggio della gerarchia: NP è Σ₁ᴾ e coNP è Π₁ᴾ. Dire NP = coNP è quindi l'ipotesi del Teorema 17.9 con i = 1, e il teorema si applica senza altri passaggi. — 1. Usa l'ipotesi $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}}$
Le due etichette in basso traducono l'ipotesi nel linguaggio della gerarchia: NP è $\htmlData{term=Σ1}{\Sigma_1^{\mathrm{P}}}$ e coNP è $\htmlData{term=Π1}{\Pi_1^{\mathrm{P}}}$ . Dire $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}}$ è quindi l'ipotesi del Teorema 17.9 con $i = 1$ , e il teorema si applica senza altri passaggi.

Applica il collasso. I riquadri in colonna sono i livelli della gerarchia, dal primo fino a Σ_kᴾ. In ognuno c'è scritto NP perché il Teorema 17.9 con i = 1 dà Σ_jᴾ = Π_jᴾ = NP per ogni j > 1. PH è l'unione di tutti i livelli, e quindi PH = NP. — 2. Applica il collasso
I riquadri in colonna sono i livelli della gerarchia, dal primo fino a $\Sigma_k^{\htmlData{term=P}{\mathrm{P}}}$ . In ognuno c'è scritto NP perché il Teorema 17.9 con $i = 1$ dà $\Sigma_j^{\htmlData{term=P}{\mathrm{P}}} = \Pi_j^{\htmlData{term=P}{\mathrm{P}}} = \htmlData{term=NP}{\mathrm{NP}}$ per ogni $j > 1$ . PH è l'unione di tutti i livelli, e quindi $\htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=NP}{\mathrm{NP}}$ .

Considera l'ipotesi più forte. La prima freccia usa la chiusura di P per complemento: una macchina deterministica si complementa scambiando accettazione e rifiuto, per cui coNP = coP = P = NP. La seconda è il caso precedente, e con NP = P tutta la gerarchia scende fino a P. Il verso opposto non si sa: da NP = coNP da sola non segue P = NP. — 3. Considera l'ipotesi più forte
La prima freccia usa la chiusura di P per complemento: una macchina deterministica si complementa scambiando accettazione e rifiuto, per cui $\htmlData{term=coNP}{\mathrm{coNP}} = \mathrm{coP} = \htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ . La seconda è il caso precedente, e con $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=P}{\mathrm{P}}$ tutta la gerarchia scende fino a P. Il verso opposto non si sa: da $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}}$ da sola non segue $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ .

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F03 n. 1 · F03 n. 7 · F04 n. 1 · F04 n. 7 · F12 n. 2 · F12 n. 5 · F14 n. 2 · G20v1 n. 4 · LU22 n. 7 · ND n. 6

Classi

P NP coNP PH

Dove: dispensa cap. 17, p. 66; slide Lez. 9

teorema

Teorema (CIRC SAT e CIRC VALIDITY)

chiesto in 3 domandedimostrato nel corso

Nella logica della Circumscription, decidere se un modello di KB soddisfa $\varphi$ (CIRC SAT) è $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ -completo; decidere se $\mathit{KB} \models_M \varphi$ (CIRC VALIDITY) è $\htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}$ -completo.

Idea, frase per l'esame e dimostrazione +

Intuizione

È SAT più una minimizzazione degli "anormali": esiste un modello tale che nessun altro modello è più normale, cioè $\exists\forall$ , secondo livello.

All'esame

Esempio di problema completo al 2° livello: CLIQUE si riduce a CIRC SAT, mentre il contrario farebbe collassare PH al primo livello.

Da scrivere all'esame

CIRC SAT è $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ -completo ( $\exists$ un modello, $\forall$ modello più normale): CLIQUE vi si riduce perché $\htmlData{term=NP}{\mathrm{NP}} \subseteq \htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ ; il contrario farebbe collassare PH al primo livello.

Dimostrazione illustrata

1 / 6

Indovina il candidato. La macchina per CIRC SAT indovina un assegnamento T, il riquadro verde, e controlla in tempo polinomiale le due spunte: T soddisfa la base KB e la formula φ della domanda. La scelta di T è il primo quantificatore, un "esiste". Resta da verificare che T sia un modello, cioè che nessun assegnamento sia strettamente più normale. — 1. Indovina il candidato
La macchina per CIRC SAT indovina un assegnamento $T$ , il riquadro verde, e controlla in tempo polinomiale le due spunte: $T$ soddisfa la base $\mathit{KB}$ e la formula $\varphi$ della domanda. La scelta di $T$ è il primo quantificatore, un "esiste". Resta da verificare che $T$ sia un modello, cioè che nessun assegnamento sia strettamente più normale.

Escludi un assegnamento più normale. Il riquadro rosso è un T' che soddisfa KB e i cui atomi anormali veri, M(T'), sono un sottoinsieme proprio di quelli di T. La croce dice che un T' così non deve esistere: è il ∀ T' scritto in alto. Cercarne uno è un problema NP, perciò la macchina lo chiede all'oracolo e accetta se la risposta è no, e CIRC SAT sta in NP^(NP) = Σ₂ᴾ. — 2. Escludi un assegnamento più normale
Il riquadro rosso è un $T'$ che soddisfa $\mathit{KB}$ e i cui atomi anormali veri, $M(T')$ , sono un sottoinsieme proprio di quelli di $T$ . La croce dice che un $T'$ così non deve esistere: è il $\forall T'$ scritto in alto. Cercarne uno è un problema NP, perciò la macchina lo chiede all'oracolo e accetta se la risposta è no, e CIRC SAT sta in $\htmlData{term=NP}{\mathrm{NP}}^{\htmlData{term=NP}{\mathrm{NP}}} = \htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ .

Codifica le variabili di QSAT₂. Nella riduzione da QSAT₂ ogni variabile diventa una coppia di atomi, x_T, x_F oppure y_T, y_F, con una clausola che ne vuole almeno uno vero. Per la variabile esistenziale un modello accende esattamente un atomo, perché con entrambi accesi basterebbe spegnere x_F per avere un assegnamento più normale; quello che resta acceso dà il valore di x. Per la variabile universale il candidato li accende entrambi, come impongono le implicazioni φ → (y_T ∧ y_F) quando vale φ. — 3. Codifica le variabili di $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_2$
Nella riduzione da $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_2$ ogni variabile diventa una coppia di atomi, $x_T, x_F$ oppure $y_T, y_F$ , con una clausola che ne vuole almeno uno vero. Per la variabile esistenziale un modello accende esattamente un atomo, perché con entrambi accesi basterebbe spegnere $x_F$ per avere un assegnamento più normale; quello che resta acceso dà il valore di $x$ . Per la variabile universale il candidato li accende entrambi, come impongono le implicazioni $\varphi \to (y_T \land y_F)$ quando vale $\varphi$ .

Usa la minimalità contro i controesempi. Se una scelta α delle y, in alto, rende falsa φ, si costruisce il T' rosso: stesse x di T, le y di α e un solo atomo acceso per ogni coppia universale. Con φ falsa le implicazioni sono vere, quindi T' soddisfa KB, e M(T') è un sottoinsieme proprio di M(T): T non è un modello. Il candidato T resta minimale solo se un α così non esiste. — 4. Usa la minimalità contro i controesempi
Se una scelta $\alpha$ delle $y$ , in alto, rende falsa $\varphi$ , si costruisce il $T'$ rosso: stesse $x$ di $T$ , le $y$ di $\alpha$ e un solo atomo acceso per ogni coppia universale. Con $\varphi$ falsa le implicazioni sono vere, quindi $T'$ soddisfa $\mathit{KB}$ , e $M(T')$ è un sottoinsieme proprio di $M(T)$ : $T$ non è un modello. Il candidato $T$ resta minimale solo se un $\alpha$ così non esiste.

Prova i due versi. A sinistra, se Phi è vera, le x della scelta vincente con tutte le coppie y_T, y_F accese danno un T che soddisfa KB e φ, ed è minimale perché nessun controesempio lo batte. A destra, un modello che soddisfa φ fissa un valore per ogni x, e la sua minimalità esclude ogni scelta delle y che renda falsa φ: quelle x rendono vera Phi. — 5. Prova i due versi
A sinistra, se $\Phi$ è vera, le $x$ della scelta vincente con tutte le coppie $y_T, y_F$ accese danno un $T$ che soddisfa $\mathit{KB}$ e $\varphi$ , ed è minimale perché nessun controesempio lo batte. A destra, un modello che soddisfa $\varphi$ fissa un valore per ogni $x$ , e la sua minimalità esclude ogni scelta delle $y$ che renda falsa $\varphi$ : quelle $x$ rendono vera $\Phi$ .

Passa alla validità. Dire che φ vale in tutti i modelli minimali equivale a dire che nessun modello minimale soddisfa ¬φ. Il riquadro scrive la stessa cosa sui problemi: CIRC VALIDITY su (KB, φ) risponde sì esattamente quando CIRC SAT su (KB, ¬φ) risponde no. Negare φ costa tempo polinomiale, e da Π₂ᴾ = coΣ₂ᴾ segue che CIRC VALIDITY è Π₂ᴾ-completo. — 6. Passa alla validità
Dire che $\varphi$ vale in tutti i modelli minimali equivale a dire che nessun modello minimale soddisfa $\neg\varphi$ . Il riquadro scrive la stessa cosa sui problemi: CIRC VALIDITY su $(\mathit{KB}, \varphi)$ risponde sì esattamente quando CIRC SAT su $(\mathit{KB}, \neg\varphi)$ risponde no. Negare $\varphi$ costa tempo polinomiale, e da $\htmlData{term=Π2}{\Pi_2^{\mathrm{P}}} = \mathrm{co}\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ segue che CIRC VALIDITY è $\htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}$ -completo.

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F03 n. 5 · G20v3 n. 1 · G20v4 n. 2

Classi

Σ₂^P Π₂^P

Problemi

SAT · VALIDITY · CIRC SAT

Dove: dispensa cap. 17, pp. 69–70; slide Lez. 9. La dispensa omette la prova (riduzione da $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_2$ ); le slide la svolgono per CIRC SAT.

teorema

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

★ chiesto in 30 domandedimostrato nel corso

Decidere se è vera una QBF $\exists X_1 \forall X_2 \exists X_3 \ldots Q X_i\, \varphi$ con i blocchi alternati di quantificatori ( $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_i$ ) è $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ -completo; il suo complemento è $\Pi_i^{\htmlData{term=P}{\mathrm{P}}}$ -completo.

Idea, frase per l'esame e dimostrazione +

Intuizione

Il numero di alternanze di quantificatori coincide con il livello della gerarchia; la difficoltà si mostra come nel Teorema di Cook.

All'esame

Dà un problema completo per ogni livello: $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_2 \to \htmlData{term=problem:QSAT}{\mathrm{QSAT}}_4$ sì; $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_4 \to \htmlData{term=problem:QSAT}{\mathrm{QSAT}}_2$ solo se PH collassa al 2° livello.

Da scrivere all'esame

Per il Teorema 17.10 $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_i$ è $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ -completo e il complemento $\Pi_i^{\htmlData{term=P}{\mathrm{P}}}$ -completo: $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_2$ si riduce a $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_4$ ( $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}} \subseteq \htmlData{term=Σ4}{\Sigma_4^{\mathrm{P}}}$ ); il contrario solo se PH collassa al 2° livello.

Dimostrazione illustrata

1 / 5

Il primo livello è SAT. Con i = 1 c'è un solo blocco, ∃ x₁, …, x_n, e la domanda diventa se esiste un assegnamento delle variabili, il riquadro verde, che rende vera φ. È SAT, e per i = 1 il teorema coincide con il Teorema di Cook-Levin. I livelli più alti aggiungono blocchi alternati davanti alla formula. — 1. Il primo livello è SAT
Con $i = 1$ c'è un solo blocco, $\exists x_1, \ldots, x_n$ , e la domanda diventa se esiste un assegnamento delle variabili, il riquadro verde, che rende vera $\varphi$ . È SAT, e per $i = 1$ il teorema coincide con il Teorema di Cook-Levin. I livelli più alti aggiungono blocchi alternati davanti alla formula.

Indovina il primo blocco. Per l'appartenenza la macchina indovina i valori del primo blocco X, in verde. Con X fissato resta ∀ Y … φ, con i-1 blocchi: la sua negazione, nel riquadro rosso, comincia con ∃ ed è un'istanza di QSATᵢ₋₁. La macchina la chiede a un oracolo di Σᵢ₋₁ᴾ e accetta se la risposta è no, quindi QSATᵢ ∈ NP^Σᵢ₋₁ᴾ = Σᵢᴾ. — 2. Indovina il primo blocco
Per l'appartenenza la macchina indovina i valori del primo blocco $X$ , in verde. Con $X$ fissato resta $\forall Y \ldots \varphi$ , con $i-1$ blocchi: la sua negazione, nel riquadro rosso, comincia con $\exists$ ed è un'istanza di $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_{i-1}$ . La macchina la chiede a un oracolo di $\Sigma_{i-1}^{\htmlData{term=P}{\mathrm{P}}}$ e accetta se la risposta è no, quindi $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_i \in \htmlData{term=NP}{\mathrm{NP}}^{\Sigma_{i-1}^{\htmlData{term=P}{\mathrm{P}}}} = \Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ .

Parti da un problema di Σᵢᴾ. Per la difficoltà si prende un L qualunque di Σᵢᴾ. Per il Corollario 2 del Teorema 17.8, x ∈ L se e solo se ∃ X₁ ∀ X₂ … Q Xᵢ vale R(x, X₁, …, Xᵢ), con stringhe di lunghezza polinomiale. La catena di riquadri è questo prefisso letto da sinistra, e R in fondo si decide in tempo polinomiale: è la parte che la riduzione trasforma in formula. — 3. Parti da un problema di $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$
Per la difficoltà si prende un $L$ qualunque di $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ . Per il Corollario 2 del Teorema 17.8, $x \in L$ se e solo se $\exists X_1\, \forall X_2 \ldots Q X_i$ vale $R(x, X_1, \ldots, X_i)$ , con stringhe di lunghezza polinomiale. La catena di riquadri è questo prefisso letto da sinistra, e $R$ in fondo si decide in tempo polinomiale: è la parte che la riduzione trasforma in formula.

Traduci il controllo in formula. Come nel Teorema di Cook-Levin, il controllo in P diventa una formula: T descrive la tabella del calcolo con variabili nuove Z, e o dice che l'uscita è 1. Le Z entrano nell'ultimo blocco, così i blocchi restano i: se l'ultimo quantificatore è ∃ si scrive ∃ Y, Z (T ∧ o), se è ∀ si scrive ∀ Y, Z (T ⇒ o). Le due forme si equivalgono perché la macchina è deterministica e ha una sola tabella corretta. — 4. Traduci il controllo in formula
Come nel Teorema di Cook-Levin, il controllo in P diventa una formula: $T$ descrive la tabella del calcolo con variabili nuove $Z$ , e $o$ dice che l'uscita è 1. Le $Z$ entrano nell'ultimo blocco, così i blocchi restano $i$ : se l'ultimo quantificatore è $\exists$ si scrive $\exists Y, Z\ (T \land o)$ , se è $\forall$ si scrive $\forall Y, Z\ (T \Rightarrow o)$ . Le due forme si equivalgono perché la macchina è deterministica e ha una sola tabella corretta.

Conserva verità e dimensione. La doppia freccia è la correttezza della riduzione: la formula costruita ψ_x è vera se e solo se x ∈ L. La sua dimensione è polinomiale in |x|, e la costruzione si fa in spazio logaritmico come quella di Cook. Con l'appartenenza, QSATᵢ è Σᵢᴾ-completo; la stessa riduzione manda il complemento di L nel complemento di QSATᵢ, che è quindi Πᵢᴾ-completo. — 5. Conserva verità e dimensione
La doppia freccia è la correttezza della riduzione: la formula costruita $\psi_x$ è vera se e solo se $x \in L$ . La sua dimensione è polinomiale in $|x|$ , e la costruzione si fa in spazio logaritmico come quella di Cook. Con l'appartenenza, $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_i$ è $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ -completo; la stessa riduzione manda il complemento di $L$ nel complemento di $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_i$ , che è quindi $\Pi_i^{\htmlData{term=P}{\mathrm{P}}}$ -completo.

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F02 n. 7 · F03 n. 1 · F03 n. 5 · F04 n. 1 · F05 n. 6 · F06 n. 2 · F07 n. 2 · F08 n. 3 · F08 n. 5 · G16 n. 4 · G16 n. 6 · F12 n. 2 · F12 n. 5 · F13 n. 1 · F13 n. 3 · F14 n. 6 · L18 n. 5 · G20v1 n. 1 · G20v2 n. 7 · G20v4 n. 1 · G20v5 n. 2 · LU22 n. 1 · GE23 n. 1 · GE23 n. 5 · FE23 n. 3 · FE23 n. 7 · SE23 n. 1 · SE23 n. 6 · E26 n. 5 · ND n. 7

Classi

Σ_i^P Π_i^P

Problemi

QSAT_i · co-QSAT_i

Dove: dispensa cap. 17, p. 70; slide Lez. 9. La dispensa lo chiama solo "Theorem" e omette la prova; il numero 17.10 e la prova vengono dalle slide. Il riepilogo del cap. 22 elenca anche il complemento di $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_i$ come $\Pi_i^{\htmlData{term=P}{\mathrm{P}}}$ -completo (la barra del complemento si perde nell'estrazione del testo).

teorema

STRATEGIC COMPANIES è $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ -completo

chiesto in 1 domandadimostrato nel corso

Una società è strategica se appartiene ad almeno un gruppo che produce tutte le merci, include le società controllate dalle società scelte e non può essere ridotto mantenendo queste condizioni. Decidere se una società è strategica è $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ -completo; il suo complemento è $\htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}$ -completo.

Idea, frase per l'esame e dimostrazione +

Intuizione

"Esiste un insieme $C'$ che contiene la società e tale che nessun suo sottoinsieme proprio va bene": un $\exists$ seguito da un $\forall$ , come $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_2$ .

All'esame

Altro problema completo al 2° livello negli esercizi di riduzione (per esempio CLIQUE si riduce al complemento di STRATEGIC COMPANIES perché $\htmlData{term=Σ1}{\Sigma_1^{\mathrm{P}}} \subseteq \htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}$ ).

Da scrivere all'esame

STRATEGIC COMPANIES è $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ -completo e il complemento $\htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}$ -completo: CLIQUE si riduce al complemento perché $\htmlData{term=Σ1}{\Sigma_1^{\mathrm{P}}} \subseteq \htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}$ ; il contrario farebbe collassare PH al primo livello.

Dimostrazione illustrata

1 / 6

Scegli un gruppo candidato. La macchina indovina un gruppo di società, il riquadro rosso: nel disegno si chiama G ed è l'insieme C' della definizione, da non confondere con l'insieme delle merci. Le frecce portano ai requisiti, tutti controllabili in tempo polinomiale. A sinistra c e le società controllate dal gruppo, che devono starci dentro; a destra le merci, che il gruppo deve produrre tutte. — 1. Scegli un gruppo candidato
La macchina indovina un gruppo di società, il riquadro rosso: nel disegno si chiama $G$ ed è l'insieme $C'$ della definizione, da non confondere con l'insieme delle merci. Le frecce portano ai requisiti, tutti controllabili in tempo polinomiale. A sinistra $c$ e le società controllate dal gruppo, che devono starci dentro; a destra le merci, che il gruppo deve produrre tutte.

Escludi gruppi più piccoli. Il gruppo deve anche essere minimo per inclusione: nessun sottoinsieme proprio H deve andare bene. Il riquadro tratteggiato è la domanda all'oracolo, "esiste un H ammissibile?", che sta in NP perché basta indovinare H e rifare i controlli. Se la risposta è no, G è minimale e la macchina accetta: è la forma ∃ G ∀ H ⊂ G scritta in alto, e il problema sta in NP^(NP) = Σ₂ᴾ. — 2. Escludi gruppi più piccoli
Il gruppo deve anche essere minimo per inclusione: nessun sottoinsieme proprio $H$ deve andare bene. Il riquadro tratteggiato è la domanda all'oracolo, "esiste un $H$ ammissibile?", che sta in NP perché basta indovinare $H$ e rifare i controlli. Se la risposta è no, $G$ è minimale e la macchina accetta: è la forma $\exists G\, \forall H \subset G$ scritta in alto, e il problema sta in $\htmlData{term=NP}{\mathrm{NP}}^{\htmlData{term=NP}{\mathrm{NP}}} = \htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ .

Codifica le variabili. Nella riduzione da QSAT₂ ogni letterale è una società: aᵢ per xᵢ e āᵢ per ¬ xᵢ. Come indicano le frecce, la merce mᵢ la producono solo loro due, quindi un gruppo che va bene ne contiene almeno una. In un gruppo minimo ne resta una sola, e quella che resta dà il valore di xᵢ. Le variabili y_j hanno la stessa coppia di società con la loro merce. — 3. Codifica le variabili
Nella riduzione da $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_2$ ogni letterale è una società: $a_i$ per $x_i$ e $\bar a_i$ per $\neg x_i$ . Come indicano le frecce, la merce $m_i$ la producono solo loro due, quindi un gruppo che va bene ne contiene almeno una. In un gruppo minimo ne resta una sola, e quella che resta dà il valore di $x_i$ . Le variabili $y_j$ hanno la stessa coppia di società con la loro merce.

Aggiungi la società speciale. La società w è quella di cui si chiede se sia strategica. Da sola controlla y_j e ¬ y_j, quindi un gruppo che contiene w deve contenere tutti e due i letterali di ogni y_j. Ogni termine della formula, che è in forma normale disgiuntiva, è a sua volta un insieme di controllo per w: se i suoi letterali sono tutti nel gruppo, cioè se il termine è soddisfatto, anche w deve entrare. — 4. Aggiungi la società speciale
La società $w$ è quella di cui si chiede se sia strategica. Da sola controlla $y_j$ e $\neg y_j$ , quindi un gruppo che contiene $w$ deve contenere tutti e due i letterali di ogni $y_j$ . Ogni termine della formula, che è in forma normale disgiuntiva, è a sua volta un insieme di controllo per $w$ : se i suoi letterali sono tutti nel gruppo, cioè se il termine è soddisfatto, anche $w$ deve entrare.

Collega minimalità e verità. A sinistra c'è un controesempio, una scelta delle y che rende falsi tutti i termini: togliendo w e il letterale falso di ogni y_j (il cerchio vuoto) resta un gruppo che va ancora bene, perché nessun termine richiama w, e quello con w non era minimo. A destra le x vengono da una scelta vincente: ogni sottoinsieme proprio che produce le merci contiene i letterali di un termine vero, la chiusura rimette w, e il gruppo con w è minimo. — 5. Collega minimalità e verità
A sinistra c'è un controesempio, una scelta delle $y$ che rende falsi tutti i termini: togliendo $w$ e il letterale falso di ogni $y_j$ (il cerchio vuoto) resta un gruppo che va ancora bene, perché nessun termine richiama $w$ , e quello con $w$ non era minimo. A destra le $x$ vengono da una scelta vincente: ogni sottoinsieme proprio che produce le merci contiene i letterali di un termine vero, la chiusura rimette $w$ , e il gruppo con $w$ è minimo.

Concludi la riduzione. La doppia freccia fra i due riquadri dice che ∃ X ∀ Y φ è vera se e solo se w è strategica. La costruzione ha una società per letterale più w, un insieme di controllo per ogni termine e quelli di w: è lineare nella formula e dà la Σ₂ᴾ-difficoltà. Con l'appartenenza vista prima STRATEGIC COMPANIES è Σ₂ᴾ-completo, e il suo complemento è Π₂ᴾ-completo. — 6. Concludi la riduzione
La doppia freccia fra i due riquadri dice che $\exists X\, \forall Y\, \varphi$ è vera se e solo se $w$ è strategica. La costruzione ha una società per letterale più $w$ , un insieme di controllo per ogni termine e quelli di $w$ : è lineare nella formula e dà la $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ -difficoltà. Con l'appartenenza vista prima STRATEGIC COMPANIES è $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ -completo, e il suo complemento è $\htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}$ -completo.

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

G20v5 n. 2

Classi

Σ₂^P Π₂^P

Problemi

Dove: dispensa cap. 17, p. 70; dispensa cap. 22, p. 85; slide Lez. 9. La dispensa omette la prova (riduzione da $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_2$ ); le slide la svolgono. Nell'esercizio 3 del cap. 17 e nel riepilogo del cap. 22 la versione $\htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}$ -completa è il complemento (barra persa nell'estrazione del testo).

teorema

Teorema 17.11 (niente problemi PH-completi)

chiesto in 4 domandedimostrato nel corso

Se esistesse un problema PH-completo, la gerarchia polinomiale collasserebbe a un livello finito.

Idea, frase per l'esame e dimostrazione +

Intuizione

Un problema PH-completo starebbe in qualche $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ ; tutto $\Sigma_{i+1}^{\htmlData{term=P}{\mathrm{P}}}$ si ridurrebbe a lui e, poiché ogni livello è chiuso rispetto alle riduzioni, $\Sigma_{i+1}^{\htmlData{term=P}{\mathrm{P}}} = \Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ .

All'esame

Serve per le risposte "solo se PH collassa" sui problemi completi per tutta PH.

Da scrivere all'esame

Per il Teorema 17.11 un problema PH-completo farebbe collassare PH a un livello finito: quindi un problema completo per PH (o per PSPACE in PH) esiste solo se PH collassa.

Dimostrazione illustrata

1 / 3

Supponi un problema PH-completo. Sia B un problema PH-completo, il punto verde. PH è l'unione infinita dei livelli impilati nel riquadro, ma un singolo problema sta in uno di essi: B ∈ Σ_kᴾ per un certo k, che da qui in avanti resta fissato. — 1. Supponi un problema PH-completo
Sia $B$ un problema PH-completo, il punto verde. PH è l'unione infinita dei livelli impilati nel riquadro, ma un singolo problema sta in uno di essi: $B \in \Sigma_k^{\htmlData{term=P}{\mathrm{P}}}$ per un certo $k$ , che da qui in avanti resta fissato.

Usa la sua difficoltà. Le frecce sono riduzioni: ogni problema A di PH si riduce a B, perché B è PH-completo. Σ_kᴾ è chiusa rispetto alle riduzioni: per decidere A si calcola la riduzione, che produce un input di lunghezza polinomiale, e su questo si esegue la macchina di B. Un polinomio di un polinomio è ancora un polinomio, e così ogni A finisce in Σ_kᴾ. — 2. Usa la sua difficoltà
Le frecce sono riduzioni: ogni problema $A$ di PH si riduce a $B$ , perché $B$ è PH-completo. $\Sigma_k^{\htmlData{term=P}{\mathrm{P}}}$ è chiusa rispetto alle riduzioni: per decidere $A$ si calcola la riduzione, che produce un input di lunghezza polinomiale, e su questo si esegue la macchina di $B$ . Un polinomio di un polinomio è ancora un polinomio, e così ogni $A$ finisce in $\Sigma_k^{\htmlData{term=P}{\mathrm{P}}}$ .

Ottieni il collasso. La freccia in alto è quanto appena visto, PH ⊆ Σ_kᴾ; quella in basso vale per definizione, perché Σ_kᴾ è uno dei livelli di PH. Insieme danno PH = Σ_kᴾ: la gerarchia collassa al livello k. Il teorema non esclude che un problema PH-completo esista, dice che esiste solo se PH collassa, e se PH collassi è una domanda aperta. — 3. Ottieni il collasso
La freccia in alto è quanto appena visto, $\htmlData{term=PH}{\mathrm{PH}} \subseteq \Sigma_k^{\htmlData{term=P}{\mathrm{P}}}$ ; quella in basso vale per definizione, perché $\Sigma_k^{\htmlData{term=P}{\mathrm{P}}}$ è uno dei livelli di PH. Insieme danno $\htmlData{term=PH}{\mathrm{PH}} = \Sigma_k^{\htmlData{term=P}{\mathrm{P}}}$ : la gerarchia collassa al livello $k$ . Il teorema non esclude che un problema PH-completo esista, dice che esiste solo se PH collassa, e se PH collassi è una domanda aperta.

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F02 n. 7 · G16 n. 1 · MA23 n. 2 · ND n. 6

Classi

PH Σ_i^P

Dove: dispensa cap. 17, p. 70; slide Lez. 9

proposizione

Proposizione 17.1 ( $\htmlData{term=PH}{\mathrm{PH}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}}$ )

★ chiesto in 18 domandedimostrato nel corso

$\htmlData{term=PH}{\mathrm{PH}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}}$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

Per ogni livello si provano tutti i certificati $y_1, \ldots, y_i$ uno alla volta riusando lo spazio: sono di lunghezza polinomiale.

All'esame

Ogni problema di PH si riduce a QSAT; non si sa se $\htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=PSPACE}{\mathrm{PSPACE}}$ .

Da scrivere all'esame

$\htmlData{term=PH}{\mathrm{PH}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}}$ (Proposizione 17.1): quindi ogni problema di PH, per esempio $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_3$ , si riduce a QSAT, che è PSPACE-completo.

Dimostrazione illustrata

1 / 3

Scrivi i blocchi di quantificatori. Un problema di PH sta in un livello fissato e, per il Corollario 2 del Teorema 17.8, si scrive con k blocchi alternati Q₁ y₁ … Q_k y_k, ognuno su stringhe di p(n) bit, davanti a un controllo R in tempo polinomiale. La fila di riquadri sotto è lo stesso prefisso, che la macchina tratta da sinistra a destra. Il numero k è fissato dal problema e non cresce con l'input. — 1. Scrivi i blocchi di quantificatori
Un problema di PH sta in un livello fissato e, per il Corollario 2 del Teorema 17.8, si scrive con $k$ blocchi alternati $Q_1 y_1 \ldots Q_k y_k$ , ognuno su stringhe di $p(n)$ bit, davanti a un controllo $R$ in tempo polinomiale. La fila di riquadri sotto è lo stesso prefisso, che la macchina tratta da sinistra a destra. Il numero $k$ è fissato dal problema e non cresce con l'input.

Prova le scelte in profondità. L'albero ha un livello per blocco e un ramo per ogni valore possibile della stringa. Una macchina deterministica prova i valori uno alla volta, nell'ordine di un contatore binario, e scende lungo il ramo verde: su un nodo ∃ le basta un figlio che riesce, su un nodo ∀ devono riuscire tutti. Finito un sottoalbero, la memoria che ha usato serve per il successivo. — 2. Prova le scelte in profondità
L'albero ha un livello per blocco e un ramo per ogni valore possibile della stringa. Una macchina deterministica prova i valori uno alla volta, nell'ordine di un contatore binario, e scende lungo il ramo verde: su un nodo $\exists$ le basta un figlio che riesce, su un nodo $\forall$ devono riuscire tutti. Finito un sottoalbero, la memoria che ha usato serve per il successivo.

Conta ciò che rimane in memoria. La colonna è il nastro in un momento qualsiasi: i valori y₁, …, y_k del ramo corrente, di p(n) bit ciascuno, e in fondo lo spazio della verifica di R, polinomiale perché una macchina non usa più celle dei passi che fa. Con k costante il totale è k · p(n) più un polinomio. Il conto vale per ogni livello, quindi PH ⊆ PSPACE, anche se il tempo può essere esponenziale. — 3. Conta ciò che rimane in memoria
La colonna è il nastro in un momento qualsiasi: i valori $y_1, \ldots, y_k$ del ramo corrente, di $p(n)$ bit ciascuno, e in fondo lo spazio della verifica di $R$ , polinomiale perché una macchina non usa più celle dei passi che fa. Con $k$ costante il totale è $k \cdot p(n)$ più un polinomio. Il conto vale per ogni livello, quindi $\htmlData{term=PH}{\mathrm{PH}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}}$ , anche se il tempo può essere esponenziale.

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F04 n. 6 · F05 n. 1 · F06 n. 1 · F07 n. 1 · F08 n. 4 · F14 n. 3 · G17 n. 5 · L18 n. 1 · G20v2 n. 2 · G20v4 n. 2 · G20v5 n. 1 · MZ22 n. 2 · LU22 n. 5 · FE23 n. 3 · MA23 n. 6 · SE23 n. 4 · E26 n. 4 · E26 n. 7

Classi

PH PSPACE

Dove: dispensa cap. 17, p. 71; slide Lez. 9. La dispensa la enuncia senza prova; le slide danno la prova (cenni).

corollario

Corollario di 17.11 ( $\htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=PSPACE}{\mathrm{PSPACE}} \Rightarrow$ collasso)

chiesto in 4 domandedimostrato nel corso

Se $\htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=PSPACE}{\mathrm{PSPACE}}$ , allora la gerarchia polinomiale collassa a un livello finito.

Idea, frase per l'esame e dimostrazione +

Intuizione

PSPACE ha problemi completi (QSAT): se PH fosse uguale a PSPACE ne avrebbe anche lei, e per il Teorema 17.11 collasserebbe.

All'esame

Per questo si pensa che $\htmlData{term=PH}{\mathrm{PH}} \neq \htmlData{term=PSPACE}{\mathrm{PSPACE}}$ ; per esempio QSAT si riduce a $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_3$ solo se PH collassa.

Da scrivere all'esame

Se $\htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=PSPACE}{\mathrm{PSPACE}}$ , QSAT sarebbe PH-completo e PH collasserebbe (Teorema 17.11): quindi QSAT si riduce a $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_3$ solo se PH collassa al 3° livello.

Dimostrazione illustrata

1 / 3

Assumi PH = PSPACE. QSAT sta in PSPACE, il riquadro rosa, che per ipotesi è uguale a PH. Allora QSAT sta in PH e quindi in un livello fissato Σ_kᴾ, il riquadro sotto. È il passo che rende l'ipotesi poco credibile: formule con quante alternanze si vuole si deciderebbero con k blocchi di quantificatori, sempre gli stessi. — 1. Assumi $\htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=PSPACE}{\mathrm{PSPACE}}$
QSAT sta in PSPACE, il riquadro rosa, che per ipotesi è uguale a PH. Allora QSAT sta in PH e quindi in un livello fissato $\Sigma_k^{\htmlData{term=P}{\mathrm{P}}}$ , il riquadro sotto. È il passo che rende l'ipotesi poco credibile: formule con quante alternanze si vuole si deciderebbero con $k$ blocchi di quantificatori, sempre gli stessi.

Applica la chiusura. Per il Teorema 17.11 un problema PH-completo fa collassare la gerarchia: Σ_kᴾ è chiusa rispetto alle riduzioni, e tutto PH entra nel livello di QSAT, come dice la freccia in alto. Quella in basso vale sempre, e si ottiene PSPACE = PH = Σ_kᴾ. Siccome si crede che PH non collassi, si crede anche che PH ≠ PSPACE, ma il corollario da solo non lo dimostra. — 3. Applica la chiusura
Per il Teorema 17.11 un problema PH-completo fa collassare la gerarchia: $\Sigma_k^{\htmlData{term=P}{\mathrm{P}}}$ è chiusa rispetto alle riduzioni, e tutto PH entra nel livello di QSAT, come dice la freccia in alto. Quella in basso vale sempre, e si ottiene $\htmlData{term=PSPACE}{\mathrm{PSPACE}} = \htmlData{term=PH}{\mathrm{PH}} = \Sigma_k^{\htmlData{term=P}{\mathrm{P}}}$ . Siccome si crede che PH non collassi, si crede anche che $\htmlData{term=PH}{\mathrm{PH}} \neq \htmlData{term=PSPACE}{\mathrm{PSPACE}}$ , ma il corollario da solo non lo dimostra.

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F04 n. 1 · F08 n. 3 · L18 n. 1 · G20v4 n. 4

Classi

PH PSPACE

Dove: dispensa cap. 17, p. 71; slide Lez. 9

teorema

QSAT è PSPACE-completo

★ chiesto in 8 domandedimostrato nel corso

Decidere se una QBF qualsiasi (senza limite alle alternanze di quantificatori) è vera è PSPACE-completo.

Idea, frase per l'esame e dimostrazione +

Intuizione

Sta in PSPACE con una valutazione ricorsiva che riusa lo spazio; per la difficoltà si codifica la raggiungibilità sul grafo delle configurazioni con QBF piccole, come il predicato PATH di Savitch.

All'esame

È il PSPACE-completo di riferimento: per esempio $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_3$ si riduce a QSAT perché $\htmlData{term=Σ3}{\Sigma_3^{\mathrm{P}}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}}$ .

Da scrivere all'esame

QSAT è PSPACE-completo: $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_3$ si riduce a QSAT perché $\htmlData{term=Σ3}{\Sigma_3^{\mathrm{P}}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}}$ , mentre il contrario implicherebbe $\htmlData{term=PSPACE}{\mathrm{PSPACE}} = \htmlData{term=Σ3}{\Sigma_3^{\mathrm{P}}}$ e il collasso di PH.

Dimostrazione illustrata

1 / 5

Valuta un quantificatore. Il nodo in alto è il quantificatore Q xᵢ. L'algoritmo prova xᵢ = 0 e poi xᵢ = 1, valuta il resto della formula e combina i due risultati: con ∃, a sinistra, basta un ramo vero, e infatti T e F danno T; con ∀, a destra, servono tutti e due veri. Il resto della formula si valuta allo stesso modo, una variabile alla volta. — 1. Valuta un quantificatore
Il nodo in alto è il quantificatore $Q x_i$ . L'algoritmo prova $x_i = 0$ e poi $x_i = 1$ , valuta il resto della formula e combina i due risultati: con $\exists$ , a sinistra, basta un ramo vero, e infatti T e F danno T; con $\forall$ , a destra, servono tutti e due veri. Il resto della formula si valuta allo stesso modo, una variabile alla volta.

Riusa lo spazio fra i rami. La visita in profondità segue un ramo alla volta, quello pieno, mentre i nodi tratteggiati non occupano memoria. Sul nastro resta la colonna a destra: i valori correnti x₁, …, x_k, uno per livello della ricorsione, più lo spazio per valutare la formula. Lo spazio è polinomiale, mentre il tempo arriva a 2ᵏ, una foglia per ogni assegnamento. — 2. Riusa lo spazio fra i rami
La visita in profondità segue un ramo alla volta, quello pieno, mentre i nodi tratteggiati non occupano memoria. Sul nastro resta la colonna a destra: i valori correnti $x_1, \ldots, x_k$ , uno per livello della ricorsione, più lo spazio per valutare la formula. Lo spazio è polinomiale, mentre il tempo arriva a $2^k$ , una foglia per ogni assegnamento.

Codifica una computazione di PSPACE. Per la difficoltà si parte da una macchina M che usa spazio n^c. Una configurazione (nastro, posizione della testina e stato) si scrive con m = O(n^c) bit, e la funzione di transizione δ porta da C_t a C_(t+1) in un passo. M accetta x se e solo se dalla configurazione iniziale C₀ si raggiunge C_(acc), e il cammino tratteggiato può avere fino a 2^m passi, perché tante sono le configurazioni. — 3. Codifica una computazione di PSPACE
Per la difficoltà si parte da una macchina $M$ che usa spazio $n^c$ . Una configurazione (nastro, posizione della testina e stato) si scrive con $m = O(n^c)$ bit, e la funzione di transizione $\delta$ porta da $C_t$ a $C_{t+1}$ in un passo. $M$ accetta $x$ se e solo se dalla configurazione iniziale $C_0$ si raggiunge $C_{\mathrm{acc}}$ , e il cammino tratteggiato può avere fino a $2^m$ passi, perché tante sono le configurazioni.

Evita di duplicare tutta la formula. Da C_s a C_t in al più 2ⁱ⁺¹ passi vuol dire che esiste un punto di mezzo C_m con due metà, φ(s, m) e φ(m, t), di al più 2ⁱ passi. Scrivere le due copie raddoppierebbe la formula a ogni livello. Il ∀ b sceglie quale metà controllare e le fa passare entrambe per l'unica copia φ(u, v); in formula, ∃ m ∀ u ∀ v [((u, v) = (s, m) ∨ (u, v) = (m, t)) → φ(u, v)]. — 4. Evita di duplicare tutta la formula
Da $C_s$ a $C_t$ in al più $2^{i+1}$ passi vuol dire che esiste un punto di mezzo $C_m$ con due metà, $\phi(s, m)$ e $\phi(m, t)$ , di al più $2^i$ passi. Scrivere le due copie raddoppierebbe la formula a ogni livello. Il $\forall b$ sceglie quale metà controllare e le fa passare entrambe per l'unica copia $\phi(u, v)$ ; in formula, $\exists m\, \forall u\, \forall v\, [((u, v) = (s, m) \lor (u, v) = (m, t)) \to \phi(u, v)]$ .

Concludi la completezza. Per ogni input x la riduzione costruisce la QBF che dice "da C₀ si arriva a C_(acc) in al più 2^m passi", con i quantificatori portati in testa come nella riga in basso; è vera se e solo se M accetta x. Ogni livello aggiunge O(m) simboli, quindi la formula resta polinomiale in |x| e QSAT è PSPACE-completo. A differenza di QSATᵢ, il numero k di blocchi cresce con l'input. — 5. Concludi la completezza
Per ogni input $x$ la riduzione costruisce la QBF che dice "da $C_0$ si arriva a $C_{\mathrm{acc}}$ in al più $2^m$ passi", con i quantificatori portati in testa come nella riga in basso; è vera se e solo se $M$ accetta $x$ . Ogni livello aggiunge $O(m)$ simboli, quindi la formula resta polinomiale in $|x|$ e QSAT è PSPACE-completo. A differenza di $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_i$ , il numero $k$ di blocchi cresce con l'input.

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F05 n. 7 · F07 n. 7 · G16 n. 6 · F13 n. 6 · L18 n. 1 · L18 n. 4 · FE23 n. 3 · SE23 n. 3

Classi

PSPACE

Problemi

QSAT

Dove: dispensa cap. 17, p. 71; slide Lez. 9. La dispensa omette la prova; le slide la svolgono.

Capitolo 20 · Crittografia e function problems

proposizione

Proposizione (FSAT e SAT)

per l'oraledimostrato nel corso

FSAT si risolve in tempo polinomiale se e solo se SAT si risolve in tempo polinomiale.

Idea, frase per l'esame e dimostrazione +

Intuizione

Con un algoritmo per SAT si fissano le variabili una alla volta: si prova $x_i = \text{vero}$ e si chiede se la formula resta soddisfacibile.

All'esame

Trovare una soluzione costa quanto decidere se esiste.

Da scrivere all'esame

Per la Proposizione su FSAT e SAT, FSAT si risolve in tempo polinomiale sse $\htmlData{term=problem:SAT}{\mathrm{SAT}} \in \htmlData{term=P}{\mathrm{P}}$ : con un decisore per SAT si fissano le variabili una alla volta.

Dimostrazione illustrata

1 / 4

Dalla ricerca alla decisione. Il riquadro rosso esegue su φ un algoritmo polinomiale per FSAT, che restituisce un assegnamento a quando la formula è soddisfacibile. Il riquadro blu valuta φ con i valori di a: se risulta vera la risposta è SAT, con la spunta verde. Se la formula non è soddisfacibile nessun a passa il controllo e la risposta è UNSAT. Il tempo è quello dell'algoritmo più una valutazione, quindi SAT sta in P. — 1. Dalla ricerca alla decisione
Il riquadro rosso esegue su $\varphi$ un algoritmo polinomiale per FSAT, che restituisce un assegnamento $a$ quando la formula è soddisfacibile. Il riquadro blu valuta $\varphi$ con i valori di $a$ : se risulta vera la risposta è SAT, con la spunta verde. Se la formula non è soddisfacibile nessun $a$ passa il controllo e la risposta è UNSAT. Il tempo è quello dell'algoritmo più una valutazione, quindi SAT sta in $\htmlData{term=P}{\mathrm{P}}$ .

Fissa la prima variabile. Nel verso opposto si ha un decisore polinomiale per SAT e si sa che φ è soddisfacibile. Il riquadro rosso gli chiede se lo è ancora φ[x₁ = 0], la formula con x₁ sostituita da 0. Se sì si fissa x₁ = 0; se no si fissa x₁ = 1 senza un'altra domanda, perché ogni assegnamento che soddisfa φ ha allora x₁ = 1, e almeno uno esiste. In entrambi i casi la formula resta soddisfacibile, come dice il riquadro verde. — 2. Fissa la prima variabile
Nel verso opposto si ha un decisore polinomiale per SAT e si sa che $\varphi$ è soddisfacibile. Il riquadro rosso gli chiede se lo è ancora $\varphi[x_1 = 0]$ , la formula con $x_1$ sostituita da 0. Se sì si fissa $x_1 = 0$ ; se no si fissa $x_1 = 1$ senza un'altra domanda, perché ogni assegnamento che soddisfa $\varphi$ ha allora $x_1 = 1$ , e almeno uno esiste. In entrambi i casi la formula resta soddisfacibile, come dice il riquadro verde.

Una variabile alla volta. La colonna ripete lo stesso passo: φ₁ = φ₀[x₁ = a₁] è la formula con x₁ fissata, poi si fissa x₂ in φ₁, e così via fino a φ_n. Ogni riquadro SAT? è una chiamata al decisore, e dopo ogni scelta la formula resta soddisfacibile. Le chiamate sono n + 1 contando quella iniziale, e nessuna formula è più lunga di φ, perché sostituire una variabile con una costante non la allunga. — 3. Una variabile alla volta
La colonna ripete lo stesso passo: $\varphi_1 = \varphi_0[x_1 = a_1]$ è la formula con $x_1$ fissata, poi si fissa $x_2$ in $\varphi_1$ , e così via fino a $\varphi_n$ . Ogni riquadro SAT? è una chiamata al decisore, e dopo ogni scelta la formula resta soddisfacibile. Le chiamate sono $n + 1$ contando quella iniziale, e nessuna formula è più lunga di $\varphi$ , perché sostituire una variabile con una costante non la allunga.

Ottieni l'assegnamento. Alla fine φ_n non ha più variabili ed è soddisfacibile, quindi è semplicemente vera: i valori scelti a = (a₁, …, a_n) soddisfano φ, come mostra la spunta sotto φ[a₁, …, a_n]. Se il decisore per SAT è polinomiale, lo è anche questa procedura. Insieme al primo verso si ottiene che FSAT si risolve in tempo polinomiale se e solo se SAT sta in P. — 4. Ottieni l'assegnamento
Alla fine $\varphi_n$ non ha più variabili ed è soddisfacibile, quindi è semplicemente vera: i valori scelti $a = (a_1, \dots, a_n)$ soddisfano $\varphi$ , come mostra la spunta sotto $\varphi[a_1, \dots, a_n]$ . Se il decisore per SAT è polinomiale, lo è anche questa procedura. Insieme al primo verso si ottiene che FSAT si risolve in tempo polinomiale se e solo se SAT sta in $\htmlData{term=P}{\mathrm{P}}$ .

Scorri l'immagine o usa Avanti.

Dimostrazione

Classi

Problemi

SAT

Dove: dispensa cap. 20, p. 81

teorema

Teorema $\mathrm{FP} = \mathrm{FNP} \iff \htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$

chiesto in 4 domandedimostrato nel corso

$\mathrm{FP} = \mathrm{FNP}$ se e solo se $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

Se $\mathrm{FP} = \mathrm{FNP}$ , FSAT è polinomiale, quindi anche SAT e allora $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ ; se $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ i function problems di NP e di P coincidono.

All'esame

Le risposte "solo se $\mathrm{FP} = \mathrm{FNP}$ " equivalgono a "solo se $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ ".

Da scrivere all'esame

$\mathrm{FP} = \mathrm{FNP}$ sse $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ (FSAT è FNP-completo e polinomiale sse $\htmlData{term=problem:SAT}{\mathrm{SAT}} \in \htmlData{term=P}{\mathrm{P}}$ ), quindi "solo se $\mathrm{FP} = \mathrm{FNP}$ " equivale a "solo se $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ ".

Dimostrazione illustrata

1 / 4

Da FP = FNP a P = NP. Con l'ipotesi FP = FNP anche FSAT ha un algoritmo polinomiale: è il riquadro verde, che dalla formula φ ricava un certificato y = f(φ). Il riquadro sotto controlla y. Se è valido φ è soddisfacibile, se un certificato non c'è non lo è. Così SAT sta in P, e siccome SAT è NP-completo, ogni problema di NP si riduce a lui e sta anch'esso in P. — 1. Da $\mathrm{FP} = \mathrm{FNP}$ a $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$
Con l'ipotesi $\mathrm{FP} = \mathrm{FNP}$ anche FSAT ha un algoritmo polinomiale: è il riquadro verde, che dalla formula $\varphi$ ricava un certificato $y = f(\varphi)$ . Il riquadro sotto controlla $y$ . Se è valido $\varphi$ è soddisfacibile, se un certificato non c'è non lo è. Così SAT sta in $\htmlData{term=P}{\mathrm{P}}$ , e siccome SAT è NP-completo, ogni problema di $\htmlData{term=NP}{\mathrm{NP}}$ si riduce a lui e sta anch'esso in $\htmlData{term=P}{\mathrm{P}}$ .

Assumi invece P = NP. La coppia (x, z) chiede se il prefisso z si può completare: esiste un y per cui il verificatore V accetta x con il certificato z · y, lungo al più p(|x|)? Nella striscia z è la parte colorata, 1 0 1, e y sono le celle con il punto di domanda. Un y si indovina e si controlla in tempo polinomiale, quindi la domanda sta in NP; con z vuoto dice se una soluzione esiste. — 2. Assumi invece $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$
La coppia $(x, z)$ chiede se il prefisso $z$ si può completare: esiste un $y$ per cui il verificatore $V$ accetta $x$ con il certificato $z \cdot y$ , lungo al più $p(|x|)$ ? Nella striscia $z$ è la parte colorata, 1 0 1, e $y$ sono le celle con il punto di domanda. Un $y$ si indovina e si controlla in tempo polinomiale, quindi la domanda sta in $\htmlData{term=NP}{\mathrm{NP}}$ ; con $z$ vuoto dice se una soluzione esiste.

Costruisci il certificato bit per bit. Con P = NP quella domanda si decide in tempo polinomiale. Si prova un valore nella cella indicata, qui 0, e si chiede se il prefisso 1 0 1 0 ha ancora un completamento valido. Se sì il bit resta e la freccia riporta alla striscia; se no si mette l'altro valore, che va bene per forza perché il prefisso precedente un completamento lo aveva. Ci si ferma quando V accetta il prefisso stesso, dopo al più p(|x|) celle. — 3. Costruisci il certificato bit per bit
Con $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ quella domanda si decide in tempo polinomiale. Si prova un valore nella cella indicata, qui 0, e si chiede se il prefisso 1 0 1 0 ha ancora un completamento valido. Se sì il bit resta e la freccia riporta alla striscia; se no si mette l'altro valore, che va bene per forza perché il prefisso precedente un completamento lo aveva. Ci si ferma quando $V$ accetta il prefisso stesso, dopo al più $p(|x|)$ celle.

Unisci i due versi. A sinistra della freccia doppia c'è la capacità di trovare in tempo polinomiale i certificati di ogni problema di FNP; a destra quella di decidere SAT in tempo polinomiale, che per la NP-completezza di SAT equivale a P = NP. Il primo verso va da sinistra a destra passando per FSAT. Il secondo, con la costruzione bit per bit, dà FNP ⊆ FP, e l'inclusione opposta vale sempre: FP = FNP ⇔ P = NP. — 4. Unisci i due versi
A sinistra della freccia doppia c'è la capacità di trovare in tempo polinomiale i certificati di ogni problema di $\mathrm{FNP}$ ; a destra quella di decidere SAT in tempo polinomiale, che per la NP-completezza di SAT equivale a $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ . Il primo verso va da sinistra a destra passando per FSAT. Il secondo, con la costruzione bit per bit, dà $\mathrm{FNP} \subseteq \mathrm{FP}$ , e l'inclusione opposta vale sempre: $\mathrm{FP} = \mathrm{FNP} \iff \htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ .

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F03 n. 6 · MZ22 n. 5 · E26 n. 3 · E26 n. 5

Classi

Dove: dispensa cap. 20, p. 81

Capitolo 21 · Oltre PSPACE

teorema

Teorema 20.1 (padding: $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}} \Rightarrow \htmlData{term=EXP}{\mathrm{EXP}} = \htmlData{term=NEXP}{\mathrm{NEXP}}$ )

chiesto in 5 domandedimostrato nel corso

Se $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ , allora $\htmlData{term=EXP}{\mathrm{EXP}} = \htmlData{term=NEXP}{\mathrm{NEXP}}$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

Si allunga ogni input $x$ fino a lunghezza $2^{|x|^k}$ con simboli di riempimento: il tempo esponenziale diventa polinomiale nella nuova lunghezza, si usa $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ e poi si torna indietro.

All'esame

Nella forma contronominale: se $\htmlData{term=EXP}{\mathrm{EXP}} \neq \htmlData{term=NEXP}{\mathrm{NEXP}}$ allora $\htmlData{term=P}{\mathrm{P}} \neq \htmlData{term=NP}{\mathrm{NP}}$ .

Da scrivere all'esame

Per il Teorema 20.1 (padding) $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}} \Rightarrow \htmlData{term=EXP}{\mathrm{EXP}} = \htmlData{term=NEXP}{\mathrm{NEXP}}$ ; quindi, per contronominale, se $\htmlData{term=EXP}{\mathrm{EXP}} \neq \htmlData{term=NEXP}{\mathrm{NEXP}}$ allora $\htmlData{term=P}{\mathrm{P}} \neq \htmlData{term=NP}{\mathrm{NP}}$ .

Dimostrazione illustrata

1 / 4

Prendi L in NEXP. Il cerchio grande è NEXP e dentro c'è un linguaggio L, deciso da una macchina nondeterministica M in tempo 2^(p(n)), con p polinomio e n = |x|. Le frecce tratteggiate che escono da M sono i rami della computazione su x, lunghi fino a 2^(p(n)) passi. L'ipotesi P = NP parla solo di tempo polinomiale, e su L così com'è non si può usare. — 1. Prendi $L$ in $\htmlData{term=NEXP}{\mathrm{NEXP}}$
Il cerchio grande è $\htmlData{term=NEXP}{\mathrm{NEXP}}$ e dentro c'è un linguaggio $L$ , deciso da una macchina nondeterministica $M$ in tempo $2^{p(n)}$ , con $p$ polinomio e $n = |x|$ . Le frecce tratteggiate che escono da $M$ sono i rami della computazione su $x$ , lunghi fino a $2^{p(n)}$ passi. L'ipotesi $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ parla solo di tempo polinomiale, e su $L$ così com'è non si può usare.

Rileggi il tempo rispetto a N. Rispetto alla nuova lunghezza N, i 2^(p(n)) passi di M sono polinomiali, anzi sono proprio N. Ne segue L' ∈ NP: una macchina controlla che il riempimento abbia la lunghezza giusta e poi simula M su x. L'ipotesi P = NP dà L' ∈ P, cioè una macchina deterministica che decide L' in tempo Nᵏ per un k fisso. — 3. Rileggi il tempo rispetto a $N$
Rispetto alla nuova lunghezza $N$ , i $2^{p(n)}$ passi di $M$ sono polinomiali, anzi sono proprio $N$ . Ne segue $L' \in \htmlData{term=NP}{\mathrm{NP}}$ : una macchina controlla che il riempimento abbia la lunghezza giusta e poi simula $M$ su $x$ . L'ipotesi $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ dà $L' \in \htmlData{term=P}{\mathrm{P}}$ , cioè una macchina deterministica che decide $L'$ in tempo $N^k$ per un $k$ fisso.

Torna alla lunghezza originale. Su input x una macchina deterministica scrive la stringa allungata, in tempo esponenziale, e poi esegue la macchina per L'. Il riquadro in alto è il tempo di quest'ultima, Nᵏ, che riscritto in n diventa (2^(p(n)))ᵏ = 2^(k · p(n)), ancora esponenziale: L ∈ EXP, e quindi NEXP ⊆ EXP (riquadro verde). Il riquadro a destra è l'inclusione opposta, ovvia perché una macchina deterministica è un caso particolare di macchina nondeterministica. — 4. Torna alla lunghezza originale
Su input $x$ una macchina deterministica scrive la stringa allungata, in tempo esponenziale, e poi esegue la macchina per $L'$ . Il riquadro in alto è il tempo di quest'ultima, $N^k$ , che riscritto in $n$ diventa $(2^{p(n)})^k = 2^{k \cdot p(n)}$ , ancora esponenziale: $L \in \htmlData{term=EXP}{\mathrm{EXP}}$ , e quindi $\htmlData{term=NEXP}{\mathrm{NEXP}} \subseteq \htmlData{term=EXP}{\mathrm{EXP}}$ (riquadro verde). Il riquadro a destra è l'inclusione opposta, ovvia perché una macchina deterministica è un caso particolare di macchina nondeterministica.

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F01 n. 5 · F03 n. 7 · F08 n. 3 · G20v4 n. 4 · E26 n. 5

Classi

P NP EXP NEXP

Dove: dispensa cap. 21, p. 83

Extra · Algoritmi probabilistici e quantistici

teorema

Teorema 11.3 ( $\htmlData{term=NP}{\mathrm{NP}} \subseteq \htmlData{term=PP}{\mathrm{PP}}$ )

chiesto in 3 domandedimostrato nel corso

$\htmlData{term=NP}{\mathrm{NP}} \subseteq \htmlData{term=PP}{\mathrm{PP}}$ , dove PP è la classe dei problemi decisi in tempo polinomiale da MdT che accettano a maggioranza dei run.

Idea, frase per l'esame e dimostrazione +

Intuizione

Si trasforma la macchina nondeterministica per $L$ in una che accetta a maggioranza e risponde come lei.

All'esame

Si pensa che il contrario non valga.

Da scrivere all'esame

$\htmlData{term=NP}{\mathrm{NP}} \subseteq \htmlData{term=PP}{\mathrm{PP}}$ (Teorema 11.3): aggiungendo metà run che accettano sempre, un solo run accettante basta per la maggioranza; il contrario si pensa che non valga.

Dimostrazione illustrata

1 / 3

Conta i rami accettanti. L'albero è la computazione su x di una macchina di NP standardizzata: p(n) livelli di scelte binarie, 0 a sinistra e 1 a destra, e 2^(p(n)) foglie, una per ramo. Le foglie verdi accettano, quelle rosa rifiutano, e A conta le verdi. In NP la domanda è solo se A > 0, e basta un ramo su 2^(p(n)), mentre PP chiede che accetti più della metà dei rami. — 1. Conta i rami accettanti
L'albero è la computazione su $x$ di una macchina di $\htmlData{term=NP}{\mathrm{NP}}$ standardizzata: $p(n)$ livelli di scelte binarie, 0 a sinistra e 1 a destra, e $2^{p(n)}$ foglie, una per ramo. Le foglie verdi accettano, quelle rosa rifiutano, e $A$ conta le verdi. In $\htmlData{term=NP}{\mathrm{NP}}$ la domanda è solo se $A > 0$ , e basta un ramo su $2^{p(n)}$ , mentre $\htmlData{term=PP}{\mathrm{PP}}$ chiede che accetti più della metà dei rami.

Aggiungi un ramo di bilanciamento. La nuova macchina lancia prima una moneta. Con 0 esegue la macchina originale, il sottoalbero di sinistra con le stesse foglie verdi e rosa; con 1 fa comunque p(n) scelte a vuoto e poi accetta, per cui a destra le foglie sono tutte verdi. Le scelte a vuoto servono a dare a tutti i rami la stessa lunghezza. I rami sono 2^(p(n)+1), e il blocco di destra ne contiene esattamente 2^(p(n)) accettanti, la metà. — 2. Aggiungi un ramo di bilanciamento
La nuova macchina lancia prima una moneta. Con 0 esegue la macchina originale, il sottoalbero di sinistra con le stesse foglie verdi e rosa; con 1 fa comunque $p(n)$ scelte a vuoto e poi accetta, per cui a destra le foglie sono tutte verdi. Le scelte a vuoto servono a dare a tutti i rami la stessa lunghezza. I rami sono $2^{p(n)+1}$ , e il blocco di destra ne contiene esattamente $2^{p(n)}$ accettanti, la metà.

Più della metà sse A > 0. La retta conta i rami accettanti della nuova macchina, da 0 a 2^(p(n)+1). Il blocco fisso porta il conteggio esattamente a 2^(p(n)), la metà, che non è ancora maggioranza; la freccia verde aggiunge gli A rami accettanti della simulazione. Si supera la metà se e solo se A > 0, cioè se e solo se x ∈ L, e la macchina lavora in tempo p(n) + 1: NP ⊆ PP. — 3. Più della metà sse $A > 0$
La retta conta i rami accettanti della nuova macchina, da 0 a $2^{p(n)+1}$ . Il blocco fisso porta il conteggio esattamente a $2^{p(n)}$ , la metà, che non è ancora maggioranza; la freccia verde aggiunge gli $A$ rami accettanti della simulazione. Si supera la metà se e solo se $A > 0$ , cioè se e solo se $x \in L$ , e la macchina lavora in tempo $p(n) + 1$ : $\htmlData{term=NP}{\mathrm{NP}} \subseteq \htmlData{term=PP}{\mathrm{PP}}$ .

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F05 n. 2 · G20v2 n. 4 · FE23 n. 2

Classi

Dove: slide Lez. 6. Solo nelle slide, non nella dispensa. PP non è tra le classi della mappa: si indica la classe collegata.

teorema

Teorema ( $\htmlData{term=PP}{\mathrm{PP}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}}$ )

chiesto in 7 domandedimostrato nel corso

$\htmlData{term=PP}{\mathrm{PP}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}}$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

Una macchina deterministica esegue uno alla volta tutti i $2^{n^c}$ run, riusando lo spazio, e conta i "yes" e i "no" con contatori di $n^c$ bit.

All'esame

Insieme agli altri risultati dà $\htmlData{term=BQP}{\mathrm{BQP}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}}$ .

Da scrivere all'esame

$\htmlData{term=PP}{\mathrm{PP}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}}$ : una MdT deterministica prova tutti i run uno alla volta riusando lo spazio e conta i "yes" con contatori binari di $n^c$ cifre.

Dimostrazione illustrata

1 / 3

Enumera i lanci casuali. Un run della macchina di PP è fissato dalla stringa r delle sue p(n) scelte binarie. Le foglie dell'albero sono queste stringhe, da 00…0 a 11…1, e il riquadro M sotto ciascuna è il run deterministico che si ottiene fissando quelle scelte. I run sono quindi 2^(p(n)), ciascuno lungo al più p(n) passi. — 1. Enumera i lanci casuali
Un run della macchina di $\htmlData{term=PP}{\mathrm{PP}}$ è fissato dalla stringa $r$ delle sue $p(n)$ scelte binarie. Le foglie dell'albero sono queste stringhe, da $00\dots0$ a $11\dots1$ , e il riquadro $M$ sotto ciascuna è il run deterministico che si ottiene fissando quelle scelte. I run sono quindi $2^{p(n)}$ , ciascuno lungo al più $p(n)$ passi.

Confronta con la metà. Il contatore c va da 0 a 2^(p(n)), un numero esponenziale che però si scrive con p(n) + 1 bit. Il segno a metà della retta, 2^(p(n)-1), è la soglia: alla fine la macchina accetta se e solo se c > 2^(p(n)-1), cioè se accetta più della metà dei run. Simulazione e contatore occupano spazio polinomiale, quindi PP ⊆ PSPACE; il tempo resta esponenziale, circa 2^(p(n)) simulazioni. — 3. Confronta con la metà
Il contatore $c$ va da 0 a $2^{p(n)}$ , un numero esponenziale che però si scrive con $p(n) + 1$ bit. Il segno a metà della retta, $2^{p(n)-1}$ , è la soglia: alla fine la macchina accetta se e solo se $c > 2^{p(n)-1}$ , cioè se accetta più della metà dei run. Simulazione e contatore occupano spazio polinomiale, quindi $\htmlData{term=PP}{\mathrm{PP}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}}$ ; il tempo resta esponenziale, circa $2^{p(n)}$ simulazioni.

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F05 n. 5 · F12 n. 3 · F12 n. 7 · G17 n. 5 · G20v3 n. 6 · GE23 n. 2 · LU24 n. 1

Classi

PSPACE

Dove: slide Lez. 6. Solo nelle slide, non nella dispensa.

proposizione

Proposizioni $\htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=BPP}{\mathrm{BPP}}$ e $\htmlData{term=BPP}{\mathrm{BPP}} \subseteq \htmlData{term=PP}{\mathrm{PP}}$

chiesto in 3 domandedimostrato nel corso

$\htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=BPP}{\mathrm{BPP}}$ e $\htmlData{term=BPP}{\mathrm{BPP}} \subseteq \htmlData{term=PP}{\mathrm{PP}}$ .

Idea, frase per l'esame e dimostrazione +

Intuizione

Una MdT deterministica ha un solo run, quindi la risposta giusta ha il 100% dei voti; la maggioranza qualificata di BPP è in particolare una maggioranza semplice.

Da scrivere all'esame

$\htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=BPP}{\mathrm{BPP}} \subseteq \htmlData{term=PP}{\mathrm{PP}}$ : un run deterministico è il 100% delle risposte, e la maggioranza qualificata ( $3/4$ ) di BPP è in particolare una maggioranza semplice.

Dimostrazione illustrata

1 / 3

Simula P senza casualità. Il riquadro è un algoritmo deterministico polinomiale A per un linguaggio di P. I bit casuali r₁, …, r_(p(n)) gli arrivano con le frecce tratteggiate, ma le croci dicono che A li ignora: dà sempre la stessa risposta, quella giusta. La probabilità di rispondere correttamente è 1, più di quanto chiede BPP, quindi P ⊆ BPP. — 1. Simula $\htmlData{term=P}{\mathrm{P}}$ senza casualità
Il riquadro è un algoritmo deterministico polinomiale $A$ per un linguaggio di $\htmlData{term=P}{\mathrm{P}}$ . I bit casuali $r_1, \dots, r_{p(n)}$ gli arrivano con le frecce tratteggiate, ma le croci dicono che $A$ li ignora: dà sempre la stessa risposta, quella giusta. La probabilità di rispondere correttamente è 1, più di quanto chiede $\htmlData{term=BPP}{\mathrm{BPP}}$ , quindi $\htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=BPP}{\mathrm{BPP}}$ .

La stessa macchina in PP. PP chiede solo che x ∈ L se e solo se la macchina accetta su più della metà dei run. La macchina di BPP lo soddisfa così com'è: sulle istanze sì accetta almeno 2/3 dei run, più della metà, e sulle istanze no al più 1/3, meno di 1/2 (la disuguaglianza in rosso). Quindi BPP ⊆ PP. Il contrario non segue, perché in PP la maggioranza può essere di un solo run. — 3. La stessa macchina in $\htmlData{term=PP}{\mathrm{PP}}$
$\htmlData{term=PP}{\mathrm{PP}}$ chiede solo che $x \in L$ se e solo se la macchina accetta su più della metà dei run. La macchina di $\htmlData{term=BPP}{\mathrm{BPP}}$ lo soddisfa così com'è: sulle istanze sì accetta almeno $2/3$ dei run, più della metà, e sulle istanze no al più $1/3$ , meno di $1/2$ (la disuguaglianza in rosso). Quindi $\htmlData{term=BPP}{\mathrm{BPP}} \subseteq \htmlData{term=PP}{\mathrm{PP}}$ . Il contrario non segue, perché in $\htmlData{term=PP}{\mathrm{PP}}$ la maggioranza può essere di un solo run.

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F12 n. 4 · F12 n. 7 · LU22 n. 6

Classi

P

Dove: slide Lez. 6. Solo nelle slide, non nella dispensa. BPP e PP non sono tra le classi della mappa completa: stanno nella mappa della scheda Probabilistiche.

proposizione

Riduzione dell'errore in BPP

chiesto in 6 domandedimostrato nel corso

In BPP la soglia $3/4$ è convenzionale: con $2k + 1$ ripetizioni e voto di maggioranza l'errore scende sotto qualunque $\varepsilon$ , con $k$ che dipende solo da $\varepsilon$ (per esempio, partendo da $3/4$ , $k = \lceil -8 \ln \varepsilon \rceil$ ). In PP invece le ripetizioni necessarie possono essere esponenziali.

Idea, frase per l'esame e dimostrazione +

Intuizione

Con una maggioranza "chiara" ogni ripetizione rende sempre più improbabile che vinca la risposta sbagliata.

All'esame

Distingue BPP (errore riducibile con poche ripetizioni) da PP (nessun metodo noto in tempo polinomiale).

Da scrivere all'esame

In BPP $2k + 1$ ripetizioni con voto di maggioranza portano l'errore sotto $\varepsilon$ , con $k = \lceil -8 \ln \varepsilon \rceil$ costante; in PP il vantaggio può essere esponenzialmente piccolo e le ripetizioni esponenziali.

Dimostrazione illustrata

1 / 4

Ripeti con monete indipendenti. Le copie di A sono esecuzioni dello stesso algoritmo sullo stesso x, ciascuna con bit casuali nuovi, e ognuna risponde 0 o 1. Ciascuna sbaglia con probabilità al più 1/3, come nel disegno, o 1/4 con la soglia 3/4: conta solo che l'errore stia sotto 1/2. Servono scelte nuove perché con le stesse scelte tutte le copie darebbero la stessa risposta. — 1. Ripeti con monete indipendenti
Le copie di $A$ sono esecuzioni dello stesso algoritmo sullo stesso $x$ , ciascuna con bit casuali nuovi, e ognuna risponde 0 o 1. Ciascuna sbaglia con probabilità al più $1/3$ , come nel disegno, o $1/4$ con la soglia $3/4$ : conta solo che l'errore stia sotto $1/2$ . Servono scelte nuove perché con le stesse scelte tutte le copie darebbero la stessa risposta.

Decidi a maggioranza. Le 2k + 1 risposte b₁, …, b_(2k+1) entrano nel riquadro della maggioranza, che restituisce il valore più frequente. Il numero dispari evita i pareggi, e la maggioranza sbaglia solo se sbagliano almeno k + 1 esecuzioni. Con errore 1/4 e tre esecuzioni, per esempio, la maggioranza sbaglia con probabilità 3 · (1/4)² · (3/4) + (1/4)³ = 10/64 approx 0,156. — 2. Decidi a maggioranza
Le $2k + 1$ risposte $b_1, \dots, b_{2k+1}$ entrano nel riquadro della maggioranza, che restituisce il valore più frequente. Il numero dispari evita i pareggi, e la maggioranza sbaglia solo se sbagliano almeno $k + 1$ esecuzioni. Con errore $1/4$ e tre esecuzioni, per esempio, la maggioranza sbaglia con probabilità $3 \cdot (1/4)^2 \cdot (3/4) + (1/4)^3 = 10/64 \approx 0{,}156$ .

Applica il limite di Chernoff. Y conta gli errori fra le 2k + 1 esecuzioni indipendenti, e la maggioranza sbaglia quando Y ≥ k + 1. Se ogni esecuzione è giusta con probabilità 1/2 + δ, il limite di Chernoff dà Pr[Y ≥ k + 1] ≤ e^(-2δ^2 k), cioè l'e^(-Omega(k)) scritto in alto quando δ è costante. La curva scende così perché in media gli errori restano sotto la metà di circa δ(2k + 1), mentre le oscillazioni casuali crescono solo come √k. — 3. Applica il limite di Chernoff
$Y$ conta gli errori fra le $2k + 1$ esecuzioni indipendenti, e la maggioranza sbaglia quando $Y \ge k + 1$ . Se ogni esecuzione è giusta con probabilità $1/2 + \delta$ , il limite di Chernoff dà $\Pr[Y \ge k + 1] \le e^{-2\delta^2 k}$ , cioè l' $e^{-\Omega(k)}$ scritto in alto quando $\delta$ è costante. La curva scende così perché in media gli errori restano sotto la metà di circa $\delta(2k + 1)$ , mentre le oscillazioni casuali crescono solo come $\sqrt{k}$ .

Scegli l'errore desiderato. Da e^(-2δ^2 k) ≤ ε viene k ≥ ln(1/ε)/(2δ²), quindi t = 2k + 1 = O(log(1/ε)) ripetizioni; con la soglia 3/4 basta k = ⌈ -8 ln ε ⌉. Se ε è costante anche t lo è e non dipende dalla lunghezza dell'input. Se ε = 2^(-poly(n)), t è polinomiale, e in entrambi i casi il tempo totale resta polinomiale. — 4. Scegli l'errore desiderato
Da $e^{-2\delta^2 k} \le \varepsilon$ viene $k \ge \ln(1/\varepsilon)/(2\delta^2)$ , quindi $t = 2k + 1 = O(\log(1/\varepsilon))$ ripetizioni; con la soglia $3/4$ basta $k = \lceil -8 \ln \varepsilon \rceil$ . Se $\varepsilon$ è costante anche $t$ lo è e non dipende dalla lunghezza dell'input. Se $\varepsilon = 2^{-\mathrm{poly}(n)}$ , $t$ è polinomiale, e in entrambi i casi il tempo totale resta polinomiale.

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F07 n. 3 · F08 n. 6 · F14 n. 5 · G20v5 n. 6 · MA23 n. 7 · SP n. 1

Dove: slide Lez. 6. Solo nelle slide, non nella dispensa.

teorema

Teorema $\htmlData{term=BQP}{\mathrm{BQP}} \subsetneq 2\text{-}\mathrm{EXP}$

per l'oraledimostrato nel corso

$\htmlData{term=BQP}{\mathrm{BQP}} \subsetneq 2\text{-}\mathrm{EXP}$ : $\htmlData{term=BQP}{\mathrm{BQP}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}} \subseteq \htmlData{term=EXP}{\mathrm{EXP}}$ , e $\htmlData{term=EXP}{\mathrm{EXP}} \subsetneq 2\text{-}\mathrm{EXP}$ per il teorema di gerarchia del tempo.

Idea, frase per l'esame e dimostrazione +

Intuizione

La catena delle inclusioni dimostrate arriva a EXP, che sta strettamente dentro 2-EXP (tempo doppiamente esponenziale).

All'esame

I problemi 2-EXP-completi non si risolvono in tempo polinomiale su un computer quantistico: è un risultato certo, non una congettura.

Da scrivere all'esame

$\htmlData{term=BQP}{\mathrm{BQP}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}} \subseteq \htmlData{term=EXP}{\mathrm{EXP}} \subsetneq 2\text{-}\mathrm{EXP}$ , quindi $\htmlData{term=BQP}{\mathrm{BQP}} \subsetneq 2\text{-}\mathrm{EXP}$ : un problema 2-EXP-completo (per esempio il ragionamento su ontologie OWL2) non si risolve in tempo polinomiale nemmeno con un calcolatore quantistico.

Dimostrazione illustrata

1 / 3

Da BQP a PSPACE. La riga in alto mette in fila due teoremi già dimostrati, BQP ⊆ PP e PP ⊆ PSPACE. La freccia fra i riquadri ne dà la conseguenza: un algoritmo quantistico con errore limitato si simula in spazio polinomiale, quindi ogni problema di BQP sta in PSPACE. La prova non usa altre proprietà del calcolo quantistico. — 1. Da $\htmlData{term=BQP}{\mathrm{BQP}}$ a $\htmlData{term=PSPACE}{\mathrm{PSPACE}}$
La riga in alto mette in fila due teoremi già dimostrati, $\htmlData{term=BQP}{\mathrm{BQP}} \subseteq \htmlData{term=PP}{\mathrm{PP}}$ e $\htmlData{term=PP}{\mathrm{PP}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}}$ . La freccia fra i riquadri ne dà la conseguenza: un algoritmo quantistico con errore limitato si simula in spazio polinomiale, quindi ogni problema di $\htmlData{term=BQP}{\mathrm{BQP}}$ sta in $\htmlData{term=PSPACE}{\mathrm{PSPACE}}$ . La prova non usa altre proprietà del calcolo quantistico.

Passa al tempo esponenziale. Una macchina deterministica che usa spazio nᵏ ha al più c^(n^k) configurazioni diverse. Il suo calcolo è la catena disegnata, C₀, C₁, …, C_t: se si ferma non passa due volte dalla stessa configurazione, altrimenti rifarebbe gli stessi passi all'infinito, quindi si ferma in meno di c^(n^k) passi. Ne segue PSPACE ⊆ EXP e, con il passo precedente, BQP ⊆ EXP. — 2. Passa al tempo esponenziale
Una macchina deterministica che usa spazio $n^k$ ha al più $c^{n^k}$ configurazioni diverse. Il suo calcolo è la catena disegnata, $C_0, C_1, \ldots, C_t$ : se si ferma non passa due volte dalla stessa configurazione, altrimenti rifarebbe gli stessi passi all'infinito, quindi si ferma in meno di $c^{n^k}$ passi. Ne segue $\htmlData{term=PSPACE}{\mathrm{PSPACE}} \subseteq \htmlData{term=EXP}{\mathrm{EXP}}$ e, con il passo precedente, $\htmlData{term=BQP}{\mathrm{BQP}} \subseteq \htmlData{term=EXP}{\mathrm{EXP}}$ .

Applica la gerarchia del tempo. La catena a sinistra porta BQP in EXP ed EXP in 2-EXP, e quest'ultima inclusione è stretta. Ogni problema di EXP sta in TIME(2^(2^n)), e il teorema di gerarchia del tempo con f(n) = 2^(2^n) dà un problema di 2-EXP fuori da questa classe. È il punto rosa: sta fuori da EXP e quindi anche da BQP, per cui BQP ⊊ 2-EXP. — 3. Applica la gerarchia del tempo
La catena a sinistra porta $\htmlData{term=BQP}{\mathrm{BQP}}$ in $\htmlData{term=EXP}{\mathrm{EXP}}$ ed $\htmlData{term=EXP}{\mathrm{EXP}}$ in $2\text{-}\mathrm{EXP}$ , e quest'ultima inclusione è stretta. Ogni problema di $\htmlData{term=EXP}{\mathrm{EXP}}$ sta in $\mathrm{TIME}(2^{2^n})$ , e il teorema di gerarchia del tempo con $f(n) = 2^{2^n}$ dà un problema di $2\text{-}\mathrm{EXP}$ fuori da questa classe. È il punto rosa: sta fuori da $\htmlData{term=EXP}{\mathrm{EXP}}$ e quindi anche da $\htmlData{term=BQP}{\mathrm{BQP}}$ , per cui $\htmlData{term=BQP}{\mathrm{BQP}} \subsetneq 2\text{-}\mathrm{EXP}$ .

Scorri l'immagine o usa Avanti.

Dimostrazione

Classi

PSPACE EXP

Dove: slide Lez. 6. Solo nelle slide, non nella dispensa. BQP e 2-EXP non sono tra le classi della mappa completa: stanno nella mappa della scheda Quantistiche.

proposizione

Proposizione (algoritmo di Grover sui problemi in NP)

chiesto in 4 domandedimostrato nel corso

Ogni problema in NP si risolve con un algoritmo quantistico con errore limitato in tempo $O(c^{n^k/2})$ , cioè circa la radice quadrata del tempo della ricerca esaustiva.

Idea, frase per l'esame e dimostrazione +

Intuizione

Grover cerca in una lista non ordinata di $m$ elementi in circa $\sqrt{m}$ passi; si applica alla ricerca del certificato.

All'esame

L'accelerazione è solo quadratica: non mette i problemi NP-completi in tempo polinomiale.

Da scrivere all'esame

Con Grover ogni problema in NP si risolve quantisticamente con errore limitato in tempo $O(c^{n^k/2})$ : accelerazione solo quadratica, il tempo resta esponenziale.

Dimostrazione illustrata

1 / 5

Descrivi i certificati. Il problema ha input x ∈ 0,1ⁿ, certificati y ∈ 0,1^(p(n)) con p polinomio e un verificatore V(x, y) che lavora in tempo polinomiale. In fondo ci sono tutti i candidati, da 0…0 a 1…1, che sono al più 2^(p(n)). Una macchina classica, nel caso peggiore, li prova tutti, e spende 2^(p(n)) volte il costo di una verifica. — 1. Descrivi i certificati
Il problema ha input $x \in \{0,1\}^n$ , certificati $y \in \{0,1\}^{p(n)}$ con $p$ polinomio e un verificatore $V(x, y)$ che lavora in tempo polinomiale. In fondo ci sono tutti i candidati, da $0\dots0$ a $1\dots1$ , che sono al più $2^{p(n)}$ . Una macchina classica, nel caso peggiore, li prova tutti, e spende $2^{p(n)}$ volte il costo di una verifica.

Rendi reversibile il controllo. Il circuito U_V calcola V(x, y) in modo reversibile, come deve fare ogni calcolo quantistico. Riceve il candidato |y⟩, un registro di lavoro in |0⟩ e un qubit in |-⟩. In uscita |y⟩ è intatto, il lavoro è tornato a |0⟩ e il risultato della verifica compare solo come segno (-1)^(V(x,y)), nel riquadro verde: i certificati validi hanno la fase cambiata, gli altri no. — 2. Rendi reversibile il controllo
Il circuito $U_V$ calcola $V(x, y)$ in modo reversibile, come deve fare ogni calcolo quantistico. Riceve il candidato $|y\rangle$ , un registro di lavoro in $|0\rangle$ e un qubit in $|-\rangle$ . In uscita $|y\rangle$ è intatto, il lavoro è tornato a $|0\rangle$ e il risultato della verifica compare solo come segno $(-1)^{V(x,y)}$ , nel riquadro verde: i certificati validi hanno la fase cambiata, gli altri no.

Amplifica i candidati validi. Il grafico vale quando un certificato valido esiste. All'inizio tutti i candidati hanno la stessa ampiezza, e la probabilità di misurarne uno valido, la barra verde, è piccola. Ogni passo di Grover usa il segno messo da U_V per aumentare un po' l'ampiezza dei validi. Dopo O(√N) interrogazioni, con N il numero di candidati, la misura restituisce un solo candidato, valido con probabilità alta. — 3. Amplifica i candidati validi
Il grafico vale quando un certificato valido esiste. All'inizio tutti i candidati hanno la stessa ampiezza, e la probabilità di misurarne uno valido, la barra verde, è piccola. Ogni passo di Grover usa il segno messo da $U_V$ per aumentare un po' l'ampiezza dei validi. Dopo $O(\sqrt{N})$ interrogazioni, con $N$ il numero di candidati, la misura restituisce un solo candidato, valido con probabilità alta.

Gestisci anche l'assenza. Il numero di certificati validi non è noto, quindi serve una variante di Grover adatta a questo caso. Il candidato y misurato si controlla classicamente con V(x, y). Se V accetta la risposta è sì, ed è certa perché y è un certificato vero. Se rifiuta la risposta è no, che sbaglia solo se x ∈ L e la ricerca ha mancato il certificato, con probabilità al più 1/3. — 4. Gestisci anche l'assenza
Il numero di certificati validi non è noto, quindi serve una variante di Grover adatta a questo caso. Il candidato $y$ misurato si controlla classicamente con $V(x, y)$ . Se $V$ accetta la risposta è sì, ed è certa perché $y$ è un certificato vero. Se rifiuta la risposta è no, che sbaglia solo se $x \in L$ e la ricerca ha mancato il certificato, con probabilità al più $1/3$ .

Calcola il costo. Con N = 2^(p(n)) candidati le interrogazioni sono O(√N) = O(2^(p(n)/2)), e ognuna costa quanto una verifica, tempo polinomiale. In totale si spende 2^(p(n)/2) · poly(n) contro 2^(p(n)) · poly(n) della ricerca esaustiva, il guadagno quadratico del riquadro verde. Il tempo resta esponenziale, perché 2^(p(n)/2) = (√2)^(p(n)), quindi Grover non porta NP in tempo polinomiale quantistico. — 5. Calcola il costo
Con $N = 2^{p(n)}$ candidati le interrogazioni sono $O(\sqrt{N}) = O(2^{p(n)/2})$ , e ognuna costa quanto una verifica, tempo polinomiale. In totale si spende $2^{p(n)/2} \cdot \mathrm{poly}(n)$ contro $2^{p(n)} \cdot \mathrm{poly}(n)$ della ricerca esaustiva, il guadagno quadratico del riquadro verde. Il tempo resta esponenziale, perché $2^{p(n)/2} = (\sqrt{2})^{p(n)}$ , quindi Grover non porta $\htmlData{term=NP}{\mathrm{NP}}$ in tempo polinomiale quantistico.

Scorri l'immagine o usa Avanti.

Dimostrazione

Dove serve nelle tracce

F03 n. 6 · G20v2 n. 6 · G20v3 n. 5 · SP n. 4

Classi