Classi di Complessita`
- problemi di decisione
- linguaggio Pascal-like
- codifiche dati “concisa”
Classi P e NP
P: classe dei problemi di decisione per la cui soluzione esistono
algoritmi deterministici di complessita` polinomiale nella
dimensione dei dati in input
NP: classe dei problemi di decisione per la cui soluzione esistono
algoritmi non deterministici di complessita` polinomiale nella
dimensione dei dati in input
Per i problemi in NP non sono ancora stati trovati algoritmi
deterministici di soluzione di complessita` polinomiale, ma
esistono algoritmi di certificazione deterministici di complessita`
polinomiale.
Si puo` allora dire che NP e` la classe dei problemi
per cui esistono certificati polinomiali.
Ovviamente P  NP, ma non si sa se la contenenza e`
propria: P  NP
oppure no: P = NP
NP
P
NP = P
Riducibilita`polinomiale
Un proplema A e` polinomialmente riducibile ad un
problema B: A  B se
Esiste una funzione f che trasforma le istanze in input per A
in istanze in input per B: f : IA  IB tale che
f sia calcolabile con un algoritmo deterministico di
complessita` polinomiale
Per ogni x  IA, A risponde “si” sull’input x se e
solo se B risponde “si” sull’input f (x)
A(x)  B(f(x))
Teorema
1. A  B and B  NP  A  NP
2. A  B and B  P  A  P
Teorema di Cook-Levin
Q: Q  NP  Q  Domino-limitato
Corollario
P = NP  Domino-limitato  P
Definizione
- Q e` NP-arduo se Q`: Q`  NP  Q`  Q
- Q e` NP-completo se 1. Q e` NP-arduo
2. Q  NP
Per dimostrare che un problema R e` NP-arduo basta dimostrare
che un problema Q NP-arduo e` polinomialmente riducibile a R
Infatti:
La relazione  e` transitiva: Q  R and R  S  Q  S
Allora:
Se Q e` NP-arduo e Q  R si ha
(Q`: Q`  NP  Q`  Q) and Q  R
Q`: Q`  NP  Q`  R, cioe` R e` NP-arduo
Domino-limitato  Cricca
Domino-limitato
Scacchiera n x n
m tessere
“ esiste una copertura della
scacchiera ?”
Cricca
Grafo G con:
- n x n x m vertici: vhij
- archi (vhij , vh’i’j’) indicano
che le tessere dh , dh’ possono
stare nelle posizioni i,j e i’,j’
“esiste una cricca di dimensione
n x n nel grafo G ?”
Domino-limitato  soddisfacibilita`
Si deve costruire una formula booleana in forma normale
congiuntiva tale che la risposta alla domanda
“ la formula e` soddisfacibile ?” sia si se e solo se “esiste una
copertura legale per la scacchiera”
Usiamo una variabile per ricordare una particolare tessera in
una particolare posizione (esattamente come i vertici nella
riduzione da Domino-limitato a Cricca): uhij
il valore true di uhij indichera` che la tessera dh e` nella
posizione i,j della scacchiera
Dovremo percio` esprimere i vincoli per una copertura legale
della scacchiera:
u00
1. d0 e` nella posizione
0
0,0
2. Esattamente una tessera in ogni posizione
2.1. Almeno una tessera in ogni posizione
and 0i,jn-1 (or 0hm-1 uhij)
2.2. Al piu` una tessera in ogni posizione
and 0i,jn-1 (and 0h,h’m-1 (not uhij or not uh’ij))
3. Escludere che due tessere dh e dh’ che non possono essere
adiacenti lo siano
3.1. orizzontalmente
and 0in-1 0jn-2 (and h,h’ (not uhij or not uh’ij+1))
3.2. verticalmente
and 0in-2 0jn-1 (and h,h’ (not uhij or not uh’i+1j))
ESEMPIO
Costruiamo la formula booleana per la seguente istanza di
Domino-limitato
Scacchiera 2 x 2
Tessere:
d0
d1
u000, u100, u001, u101, u010, u110, u011, u111
1
u000
and
2.1 ( (u000or u100)and (u010 or u110) and (u001or u101) and (u011or u111) )
and
2.2
3.1
3.2
( (not u000 or not u100) and (not u010 or not u110) and
(not u001 or not u101) (not u011 or not u111) and ) and
( (not u000or not u001) and (not u010 or not u011)
and (not u100 or not u101) and (not u110 or not u111) ) and
( (not u000or not u010) and (not u001 or not u011)
and (not u100 or not u110) and (not u101 or not u111) )
La formula risulta vera per la seguente assegnazione di valori
di verita` alle variabili:
u000 = true
u110 = true
u100 = false
u010 = false
u101 = true
u011 = true
u001 = false
u111 = false
u000 and ((u000 or u100) and (u001or u101) and (u010 or u110) and
(u011or u111) ) and ( ( not u000 or not u100) and ( not u001 or
not u101) and (not u010 or not u110) and (not u011 or not u111) )
and ( (not u000 or not u001) and (not u010 or not u011) and (not
u100 or not u101) and (not u110 or not u111) ) and ( (not u000 or
not u010) and (not u001 or not u011) and (not u100 or not u110) and
(not u101 or not u111) )
Problemi in NP
Teorema di Cook-Levin
Domino-limitato
Cricca
Soddisfacibilità
Insieme
indipendente
Circuito
Hamiltoniano
Commesso
Viaggiatore
Partizione
Scheduling
Multiprocessore
Zaino
Somma di
Sottinsieme
Insieme indipendente: Dati G non orientato e k intero positivo
“Esiste un sottoinsieme di almeno k vertici mutuamente non
connessi da archi ?”
Cricca

Insieme indipendente
G non orientato
Gc non orientato
V
Vc = V
E
Ec = {(u, w) / (u, w)  E}
“Esiste un sottoinsieme di
almeno k vertici a coppie
connessi da archi ?”
“Esiste un sottoinsieme di
almeno k vertici mutuamente
non connessi da archi ?”
Circuito Hamiltoniano: Dato G non orientato
“Esiste un ciclo che attraversi ogni vertice una e una sola volta ?”
Circuito Hamiltoniano
G non orientato
V
E

Commesso viaggiatore
Gcomp non orientato
Vcomp = V
Ecomp = {(r, t) /  r, t
Vc}
W(u,v) = 1 se (u,v) E
W(u,v) = 2 se (u,v)  E
“Esiste in G un ciclo che
attraversa ogni vertice una
e una sola volta ?”
“Esiste un percorso di costo
al massimo uguale al numero
di vertici?”
Partizione: Dato un insieme di interi positivi A = {a1, a2,…, an}
“esiste un sottoinsieme S degli indici {1, 2,…, n} tale che
iS ai = iS ai ?”
Partizione
Scheduling
Multiprocessore
Zaino
Somma di
Sottinsieme
Scheduling multiprocessore: Dati n programmi {p1, p2,…, pn},
ognuno dei quali, pi, richiede tempo d’esecuzione ti, intero positivo,
m processori identici e un intero d.
“E` possibile eseguire tutti i programmi in al piu` d unita` di
tempo ?”
Partizione
A = {a1, a2,…, an}

Scheduling multiprocessore
t i = ai
m=2
d = (1/2) i{1,…,n} ai
“esiste un sottoinsieme S
degli indici {1, 2,…, n}tale
che iS ai = iS ai ?”
“E` possibile eseguire tutti i
programmi in al piu` d unita`
di tempo ?”
Zaino: Dati un insieme O = {o1, o2,…, on} di oggetti, ad
ognuno dei quali, oi, sono associati un profitto pi e un volume vi,
interi positivi, due interi positivi c (capacita`) e k (obiettivo)
“esiste un sottoinsieme S degli indici {1, 2,…, n} tale che
i  S vi  c e i  S pi  k ?”
Partizione
A = {a1, a2,…, an}

Zaino
pi = vi = ai
c = k = (1/2) i{1,…,n} ai
“esiste un sottoinsieme S
degli indici {1, 2,…, n}tale
che iS ai = iS ai ?”
“esiste un sottoinsieme S degli
indici {1, 2,…, n}tale che
i  S vi  c e i  S pi  k ?”
Somma di sottoinsieme: Dati un insieme di interi A = {a1, a2,…,
an} e un intero positivo k
“esiste un sottoinsieme S degli indici {1, 2,…, n} tale che
i  S ai = k ?”
Partizione
A = {a1, a2,…, an}

Somma di sottoinsieme
A = {a1, a2,…, an}
k = (1/2) i{1,…,n} ai
“esiste un sottoinsieme S
degli indici {1, 2,…, n}tale
che iS ai = iS ai ?”
“esiste un sottoinsieme S degli
indici {1, 2,…, n}tale che
i  S ai = k ?”
P  EXP
P-SPAZIO  EXP-SPAZIO  E
NP  NEXP
EXP-SPAZIO
NEXP
EXP
P-SPAZIO
NP-completi
NP
P
E