Le risorse del calcolo

Classi di complessità

Separazioni dimostrate Questioni aperte

inclusione dimostrata, non si sa se stretta

inclusione stretta dimostrata

separazione dimostrata tra classi lontane

non si sa nemmeno se una contiene l'altra

\htmlData{term=NP}{\mathrm{NP}}

Tempo polinomiale nondeterministico

= \htmlData{term=Σ1}{\Sigma_1^{\mathrm{P}}}

chiusa per complemento: non si sa (

\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}}

è aperto)

Confronta con…

I problemi in cui una risposta sì ha un certificato corto, che si controlla in tempo polinomiale. Trovare il certificato può essere difficile, controllarlo è facile: come la combinazione di una cassaforte, che si verifica subito se qualcuno te la dice.

Vedi NP nei piani di PH →

Dove sta: inclusioni e questioni aperte

È contenuta in

\subseteq

\subseteq

Δ₂^P

\subseteq

Σ₂^P

\subseteq

Π₂^P

\subseteq

Σ_i^P

\subseteq

Π_i^P

\subseteq

\subseteq

PSPACE

\subseteq

EXP

\subsetneq

NEXP

\subsetneq

\subsetneq

\subsetneq

coRE

Contiene

\supseteq

\supseteq

\supseteq

\supseteq

NP ∩ coNP

Rapporto non noto

?

coNP

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

Problemi completi

$\htmlData{term=problem:SAT}{\mathrm{SAT}} = \htmlData{term=problem:QSAT}{\mathrm{QSAT}}_1$ (Cook-Levin), 3-SAT, CLIQUE, INDEPENDENT SET, NODE COVER, HAMILTON PATH, TSP(D), 3-COLORING, KNAPSACK e gli altri della Lez. 8.

Problemi: SAT · 3-SAT · MAX2SAT · CIRCUIT SAT · CLIQUE · INDEPENDENT SET · NODE COVER · HAMILTON PATH · TSP(D) · 3-COL · INTEGER PROGRAMMING · KNAPSACK

Teoremi su NP

Proposizione $\mathrm{P} \subseteq \mathrm{NP}$ · Teorema (da nondeterministico a deterministico) · Gerarchie nondeterministiche · Teorema 7.4 (a) · Teorema 7.4 (b) · Corollario (catena $\mathrm{L} \subseteq \mathrm{NL} \subseteq \mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE}$ ) · Chiusura delle classi rispetto alle riduzioni · Proposizione (un problema completo per due classi) · Corollario (classe piccola con un problema completo per la grande) · Teorema di Cook-Levin · 3-SAT è NP-completo · Proposizione 9.1 (certificati succinti) · MAX2SAT è NP-completo · INDEPENDENT SET è NP-completo · Corollario: CLIQUE e NODE COVER sono NP-completi · HAMILTON PATH è NP-completo · TSP(D) è NP-completo · 3-COLORING è NP-completo ( $\mathrm{2\text{-}COLORING} \in \mathrm{P}$ ) · TRIPARTITE MATCHING è NP-completo · Corollario: EXACT COVER BY 3-SETS, SET COVERING e SET PACKING sono NP-completi · INTEGER PROGRAMMING è NP-completo · KNAPSACK è NP-completo · Proposizione (KNAPSACK in tempo $O(nW)$ ) · NP-completezza in senso forte · Proposizione B (complemento di un NP-completo) · Proposizione C (chiusura dei complementi) · Proposizione D (un $C$ -completo in $\mathrm{co}C$ ) · Se $\mathrm{P} = \mathrm{NP}$ allora $\mathrm{NP} = \mathrm{coNP}$ · EXACT TSP è NP-hard (varianti di TSP) · Oracoli inutili e $\mathrm{DP} \subseteq \mathrm{P}^{\mathrm{NP}}$ · Corollario (collasso al primo livello) · Teorema (complessità delle query ai database relazionali) · FSAT è FNP-completo · Proposizione (FSAT e SAT) · Teorema $\mathrm{FP} = \mathrm{FNP} \iff \mathrm{P} = \mathrm{NP}$ · Teorema 20.1 (padding: $\mathrm{P} = \mathrm{NP} \Rightarrow \mathrm{EXP} = \mathrm{NEXP}$ ) · Teorema 11.3 ( $\mathrm{NP} \subseteq \mathrm{PP}$ ) · Proposizione (algoritmo di Grover sui problemi in NP)

Dalle tracce d'esame

\htmlData{term=Σ1}{\Sigma_1^{\mathrm{P}}} \subseteq 2\text{-}\mathrm{EXP}

? (E26)

SÌ

\htmlData{term=Σ1}{\Sigma_1^{\mathrm{P}}} = \htmlData{term=NP}{\mathrm{NP}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}} \subseteq \htmlData{term=EXP}{\mathrm{EXP}} \subseteq 2\text{-}\mathrm{EXP}

È vero che CLIQUE non appartiene a NEXP? (F02)

\htmlData{term=problem:CLIQUE}{\mathrm{CLIQUE}} \in \htmlData{term=NP}{\mathrm{NP}} \subseteq \htmlData{term=NEXP}{\mathrm{NEXP}}

\htmlData{term=problem:CLIQUE}{\mathrm{CLIQUE}} \in \htmlData{term=Σ1}{\Sigma_1^{\mathrm{P}}}

? (F07)

SÌ

\htmlData{term=Σ1}{\Sigma_1^{\mathrm{P}}} = \htmlData{term=NP}{\mathrm{NP}}

e CLIQUE è NP-completo

È vero che

\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_1

non appartiene a

\htmlData{term=Σ4}{\Sigma_4^{\mathrm{P}}}

? (F14)

\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_1 \in \htmlData{term=Σ1}{\Sigma_1^{\mathrm{P}}} \subseteq \htmlData{term=Σ4}{\Sigma_4^{\mathrm{P}}}

È vero che

\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_1 \notin 2\text{-}\mathrm{EXP}

? (L18)

\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_1 \in \htmlData{term=NP}{\mathrm{NP}} \subseteq 2\text{-}\mathrm{EXP}

CLIQUE si può risolvere in

O(2^{n/2})

? (L18)

SÌ

$m$ è il numero di nodi; $n$ è la lunghezza dell’intero input in bit. Il limite richiesto usa

n

, non

m

.

1. Quanto è grande l’input? Con la codifica tramite matrice di adiacenza, un grafo di

m

nodi richiede

m

righe e

m

colonne: almeno

m^2

bit, uno per ogni cella. Quindi

n \ge m^2

m \le \sqrt{n}

.

2. Che algoritmo usiamo? Proviamo tutti i

2^m

gruppi di nodi. Per ogni gruppo controlliamo che contenga almeno

K

nodi e che ogni coppia sia collegata. Il controllo richiede tempo polinomiale, quindi il totale è al più

2^{\sqrt{n}} \cdot \mathrm{poly}(n)

.

3. Perché basta? Per

n

abbastanza grande,

\sqrt{n}

cresce molto più lentamente di

n/2

. Anche includendo il costo polinomiale dei controlli, il tempo rimane entro

O(2^{n/2})

: infatti

\sqrt{n} + k\log_2 n \le n/2

per ogni

k

fissato, da un certo

n

in poi.

Esempio: con 10 nodi, la sola matrice ha 100 celle. I gruppi da provare sono

2^{10} = 1.024

, mentre

2^{n/2}

è almeno

2^{50}

. La differenza nasce dal fatto che

n

conta i bit della descrizione.

Altre 4 nel quiz →

Fonti: dispensa cap. 3, 5, 12–13, 22; appunti Lez. 3, 7, 8