Trattabilità computazionale.
Tesi di Cobham. Tutti i modelli di calcolo introdotti per defnire la
calcolabilità in tempo polinomiale hanno al più lo stesso potere
computazionale delle MT operanti in tempo polinomiale.
Quindi defniamo trattabili i problemi che possono essere risolti in tempo
polinomiale con MT.
Motivazioni:
- la classe P è una classe "stabile", cioè invariante per diversi modelli di
calcolo.
- la forte differenza nell'andamento asintotico delle funzioni polinomiali
rispetto a quelle esponenziali. Un aumento della potenza di calcolo degli
elaboratori si rifette nel primo caso in un fattore moltiplicativo della
lunghezza delle istanze risolubili in una determinata quantità di tempo mentre
nel caso di tempi esponenziali si ha solo il benefcio di un termine additivo
(Fig. 9.1- 9.3).
Per moltissimi problemi di interesse pratico non sappiamo stabilire se sono
risolubili in tempo polinomiale. Sappiamo però che sono risolubili in tempo
polinomiale con NDMT. La mancanza di separazione tra NP ed P non ci
consente quindi di stabilire se essi siano o non siano "trattabili".
M. R. Garey/D. S. Johnson :
COMPUTER AND INTRACTABILITY
A guide to the Theory of NP-Completeness”
Freeman and Company ( 1979)
Riducibilità fra problemi decisionali
Def. Un problema P è Karp-riducibile ad un problema Q
P ≤m Q
se esiste un algoritmo R che trasforma ogni istanza x di P in una istanza y di
Q in modo che x ∈ YP ⇔ y ∈ YQ; R è chiamata una Karp-riduzione da P a Q.
Oss. 1. Se P ≤m Q ed esiste un algoritmo B per decidere Q, possiamo costruire
un algoritmo A per decidere P:
- data x ∈ I P applico R a x ed ottengo y ∈ I Q
- applico B ad y; se B ritorna SI anche A ritorna SI altrimenti ritorna NO.
La complessità di A dipende da quella di B e di R.
Oss. 2. Se P ≤m Q possiamo dedurre una relazione tra la complessità dei
problemi. Intuitivamente: comp (P) ≤ comp (Q) + comp (R).
In questo modo quando non possiamo stabilire la complessità "assoluta" di un
problema possiamo stabilire relazioni di complessità relativa.
Def. Un problema P è polinomialmente Karp-riducibile a Q
P ≤p m Q
se è Karp-riducibile e l'algoritmo R è di complessità polinomiale nella
lunghezza delle istanze.
Oss. Se P ≤pm Q
- e so risolvere in tempo polinomiale Q allora so risolvere in tempo
polinomiale anche P
- e posso dimostrare che non esiste un algoritmo polinomiale per P ne segue
che non può esistere un algoritmo polinomiale per Q.
Quando non ci sono dubbi sul tipo di riduzione invece di P ≤ pm Q scriveremo
semplicemente P ≤ Q.
Completezza
È uno strumento per indagare relazioni di inclusione fra classi di complessità.
Def. Data una classe di complessità C ed una riducibilità ≤r tra problemi,
diciamo che un problema Q ∈ C è C-completo rispetto ad ≤r se per ogni
problema P ∈ C si ha che P ≤r Q.
Def. Un problema Q ∈ NP è NP-completo se per ogni problema P ∈ NP si ha
che P ≤ pm Q.
Oss. Se si riuscisse a dimostrare che un problema NP-completo Q appartiene
alla classe P allora ogni altro problema P di NP sarebbe risolvibile in tempo
polinomiale con un algoritmo deterministico. Infatti da P ≤ pm Q, se Q fosse
risolubile in tempo polinomiale anche il problema P lo sarebbe.
• Nessuno è mai riuscito a risolvere un problema NP-completo con un
algoritmo polinomiale deterministico.
• Nessuno è mai riuscito a dimostrare un lower bound non polinomiale (es.
Ω(nlog n) per un problema di NP.
• chiunque scommetterebbe che P ≠ NP.
La classe NP
Classe dei problemi risolvibili in tempo polinomiale da un algoritmo (MT)
non deterministico. Questa classe vuole isolare la nozione di “verifcabilità”
in tempo polinomiale.
Cerchiamo problemi in NP.
Sia:
X = {x1,..., xn}
insieme di variabili booleane
T(X) = {x1,..., xn, ~x1,..., ~xn} insieme di letterali
C = l1 ∨ l2 ∨.. lni
clausola (è disgiunzione di più letterali)
F = {C1, C2, ..., Cm}
formula (è congiunzione di più clausole).
Una assegnazione di verità su X è una funzione f: X → {true, false}. Si dice
che f soddisfa una variabile xi se f(xi) = true, soddisfa ~xi se f(xi) =false,
soddisfa una clausola C se soddisfa un letterale l ∈ C, soddisfa una formula F
se soddisfa tutte le sue clausole.
SAT: Problema della soddisfacibilità di una formula booleana F in forma
normale congiuntiva (CNF).
Istanza: formula booleana F in CNF su un insieme X di variabili booleane.
Predicato: esiste un'assegnazione di verità f su X che soddisfa F?
Es.
F = {p∨q∨~r, ~p∨q∨r, ~q∨~r, ~p∨r}
F è soddisfatta da: f(p) = f(r) = true, f(q) = false.
F = {p∨q, ~p∨q, p∨~q, ~p∨~q}
non è soddisfacibile da alcuna assegnazione di verità su {p,q}.
Teorema. SAT ∈ NP.
Dim. Possiamo costruire una MTND M che risolve SAT in tempo polinomiale:
facciamo generare ad M tutte le possibili assegnazioni di verità su X (sono
in numero esponenziale ma le possiamo generare nondeterministicamente
in tempo polinomiale);
associamo ad ogni assegnazione un cammino radice-foglia dell'albero di
computazione di M;
ogni nodo dell'albero è associato alla scelta vero/falso per una variabile;
ogni cammino radice-foglia è di lunghezza polinomiale;
su ogni foglia verifchiamo in tempo polinomiale se l'assegnazione
prodotta soddisfa F.
PL{0,1}. Problema della programmazione lineare in {0,1}
Istanza: insieme di variabili Z = {z1,..., zn} con dominio in {0,1}; insieme D
di disequazioni lineari su Z.
Predicato: esiste un'assegnazione di valori alle variabili di Z che verifca tutte
le disequazioni in D?
Teorema. PL{0,1} ∈ NP
Dim. Realizziamo una macchina non deterministica che genera in tempo O(n)
tutte i possibili vettori con valori in 0 o 1 e poi, alla foglia di ogni ramo
dell'albero, verifca se il vettore soddisfa tutti i vincoli.
Teorema. SAT ≤ mp PL{0,1}
Dim. Ogni istanza xSAT = < X, F > di SAT può essere ridotta ad una istanza
xPL{0,1} = < Z, D > di PL{0,1}.
Se Ci = li1∨...∨ lik è la i-esima clausola di F defniamo la i-esima disequazione
di I: τi1+...+ τik > 0 con:
τij = zk
se
lij = xk
τij=1-zk
se
lij = ~xk
Ogni assegnazione di valori di verità f su X soddisfa F se e solo se tutte le
disequazioni di I sono verifcate dalla assegnazione f': Z → {0,1} tale che:
f'(zi) = 1 se e solo se f(xi) = vero
La riduzione è chiaramente calcolabile in tempo polinomiale.
INDSET. Problema dell’insieme indipendente.
Istanza: grafo G = (V, E), intero k > 0.
Predicato: esiste un sottoinsieme U di V con |U| ≥ k tale che per ogni u, v ∈U
(u,v) ∉ E?
Teorema. INDSET ∈ NP
Dim. Generiamo con una MTND tutti i sottoinsiemi di V, uno per ogni
cammino radice-foglia dell'albero di computazione.
Per ogni sottoinsieme U di V verifchiamo in tempo polinomiale:
(1) se U è un insieme indipendente;
(2) se |U| ≥ k
NOTA BENE. Per dimostrare che un problema Q in NP è NP-completo ci
sono due possibili metodi:
1. dimostrare che ogni problema P in NP è riducibile a Q, oppure:
2. trovare un problema P che si è già dimostrato NP-completo e dimostrare
che P ≤pm Q; infatti, se P ≤pm Q allora per ogni P1 ∈ NP, poiché si sa che P1
≤pm P, si avrebbe anche che P1 ≤pm Q.
Perchè il metodo 2 sia applicabile c'è bisogno di individuare almeno un primo
problema NP-completo.
Teorema di Cook. SAT è NP-completo.
Dim. Abbiamo già dimostrato che SAT ∈ NP; ora dimostriamo che per ogni
problema decisionale P ∈ NP si ha che P ≤ SAT.
Dato un problema P ∈ NP esiste una MTND che in tempo polinomiale accetta
il linguaggio LP associato a P (codifica di istanze yes); sia M una MTND che
per ogni x ∈ Γ* accetta x in tempo p(|x|), con p polinomio, se e solo se x ∈ LP.
Data una stringa x ∈ Γ* costruiamo una formula w in CNF tale che w e'
soddisfacibile ⇔ M accetta x in tempo p(|x|), cioè ⇔ x ∈ Lp.
Ipotesi semplifcative:
M ha nastro semi-infnito; nella confgurazione iniziale x è nelle prime celle;
ogni confgurazione utilizza esattamente p(|x|) celle; esiste un solo stato q Y di
accettazione; la computazione esegue esattamente p(|x|) passi.
Inoltre supponiamo:
Q = {q0, qY = q1,..., qr }
Γb = {a0 = b, a1,..., aη }
w e' congiunzione di quattro formule
w = wT ∧ wM ∧ wI ∧ wF
wT
wM
wI
wF
specifca le proprietà generali delle MT
specifca la funzione di transizione di M.
specifca la confgurazione iniziale
specifca la confgurazione fnale
Variabili di w:
Q(t, k) è true ⇔ all'istante t la macchina M si trova nello stato qk
0 ≤ t ≤ p(|x|),
0≤k≤ r
H(t, i) è true ⇔ all'istante t la testina di M si trova sulla cella i del nastro
0 ≤ t ≤ p(|x|),
0 ≤ i ≤ p(|x|)
C(t, i, h) è true ⇔ all'istante t la cella i del nastro contiene il simbolo ah
0 ≤ t ≤ p(|x|), 0 ≤ i≤ p(|x|), 0 ≤ h ≤ η
Quando diciamo “ all'istante i” intendiamo “dopo i steps”.
Le variabili sono O(p(|x|)2).
wI e wF si costruiscono così:
se x=ah0, a h1,...., ahn-1
se q0 è lo stato iniziale (e a0 = b)
wI = Q(0, 0) ∧ H(0, 0)∧
C(0, 0, h0)∧....∧ C(0, n-1, hn-1)∧...
C(0, n, 0) ∧....∧ C(0, p(|x|), 0)
wF = Q(p(|x|), 1) se qY = q1
wT
e' congiunzione di tre formule:
wT = wTS ∧ wTH ∧ wTC
wTS
specifca che ad ogni istante M si trova in esattamente uno stato
wTS = ∧ [∨ Q(t, k) ∧ (~Q(t, k1)∨~Q(t, k2)) ]
t k
k1 ≠ k2
wTH specifca che ad ogni istante la testina si trova su esattamente una cella
del nastro
wTH = ∧ [∨ H(t, i) ∧ (~H(t, i1)∨~H(t, i2))]
t i
i1 ≠ i 2
wTC
specifca che ad ogni istante ogni cella del nastro contiene un solo
carattere
wTC = ∧ [∨ C(t, i, h) ∧ (~C(t, i, h1) ∨~C(t, i, h1))]
t, i h
h1 ≠ h2
Si ha che:
|wT| = O(p(|x|))+O(p3(|x|))+O(p2(|x|)) = O(p3(|x|))
Infne wM e' la congiunzione di due formule
wM = wM1 ∧ wM2
Le due formule che costruiamo non sono in CNF, ma possono essere
trasformate in CNF con un aumento lineare della lunghezza; |wM| = O(p2(|x|)).
wM1 specifca che i contenuti del nastro agli istanti t e t+1 sono gli stessi,
eccetto, al più, per ciò che riguarda la cella su cui la testina è posizionata
all'istante t :
wM1 =
∧ [H(t, i) ∨ ∧ (C(t, i, h) ⇒ C(t+1, i, h)) ]
t, i
h
=
∧ [H(t, i)∨((¬C(t, i, 0) ∨ C(t+1, i, 0)) ∧....∧ (¬C(t, i, η) ∨ C(t+1, i, η)))]
t, i
=
∧ [(H(t, i) ∨ ¬C(t, i, 0) ∨ C(t+1, i, 0))∧....
…∧(H(t, i) ∨ ¬C(t, i, η) ∨ C(t+1, i, η))]
t, i
wM2
codifca la funzione di transizione di M e consta della congiunzione di
p2(|x|) . |Q| . (|Σ|+1) formule, ciascuna di O(1) letterali
Se δ(qk, aj) = {(ql1, ah1, d), …, (qld, ahd, d)} allora wM2 contiene:
∧
(~H(t, i)∨~Q(t, k)∨~C(t, i, j) ∨
t, i
H(t+1, i+1) ∧ Q(t+1, l1) ∧ C(t+1, i , h1) ∨...
H(t+1, i+1) ∧ Q(t+1, ld) ∧ C(t+1, i , hd) )
Osservare che:
~H ∨ ~Q ∨ ~C ∨ ( x1 ∧ y1 ∧ z1 ) ∨.....∨ ( xd ∧ yd ∧ zd ) =
{~H ∨ ~Q ∨ ~C ∨ Z1 ∨.....∨ Zd
Zi ⇔ ( xi ∧ yi ∧ zi ) i=1,..., d
[~ Zi ∨ ( xi ∧ yi ∧ zi )]
con l'aggiunta di:
che equivalgono a:
∧ [Zi ∨ ~( xi ∧ yi ∧ zi )]
[(~ Zi ∨ xi ) ∧ (~ Zi ∨ yi) ∧ (~ Zi ∨ xi)] ∧ [(Zi ∨ ~xi ∨ ~ yi ∨ ~ zi)] i=1,..., d}
In conclusione la formula w ha lunghezza O(p3(|x|)) e può essere costruita in
tempo proporzionale alla sua lunghezza.
Inoltre w è soddisfacibile, cioè w ∈ LSAT, se e solo se M accetta la stringa x in
tempo p(|x|), cioè x ∈ LP.
Altri problemi NP-completi
ES 1. 3-soddisfacibilità (3-SAT)
Istanza: formula F in CNF su un insieme X di variabili booleane con ogni
clausola composta esattamente da 3 letterali.
Predicato: esiste un'assegnazione f: X -> {true, false} che soddisfa F?
Riduzione: SAT ≤ 3-SAT
ES 2. Copertura degli archi di un grafo con nodi (VERTEX-COVER)
Istanza: grafo G = (V, E), intero k>0.
Predicato: esiste un sottoinsieme U di V con |U| ≤ k tale che se (u,v) ∈ E
almeno uno tra u e v è in U ?
Riduzione: 3-SAT ≤ VERTEX-COVER
ES 3. Circuito Hamiltoniano (HCIRCUIT)
Istanza: grafo G = (V, E)
Predicato: G contiene un circuito Hamiltoniano?
Riduzione: VERTEXCOVER ≤ HCIRCUIT
N.B: il problema del circuito Euleriano è invece polinomiale.
ES 4. Problema del commesso viaggiatore (TSP)
Istanza: grafo completo G = (V, E), ∀ a ∈ E un peso w(a) ∈ N+, B ∈ N+
Predicato: G contiene un circuito Hamiltoniano di peso al più B?
Riduzione: HCIRCUIT ≤ TST con pesi in {1, 2}.
NP-Completezza in senso forte
Lunghezza di una istanza di un problema: numero di caratteri necessari a
rappresentarla in uno schema di codifica predefinito.
Massimo di una istanza di un problema: grandezza del più grande numero
presente nell’istanza, altrimenti zero.
Due coppie di funzioni di lunghezza e di massimo per un problema sono
polinomialmente correlate se esistono due polinomi p, p’ tali che, per ogni
istanza I del problema :
len(I)
max(I)
≤ p’(len’(I))
≤ p’(len’(I), max’(I))
len’(I)
max’(I)
≤ p (len(I))
≤ p (len(I), max(I))
Per i problemi NP-completi non sappiamo se esiste un algoritmo polinomiale
di soluzione. Per alcuni di essi ne esiste invece uno pseudopolinomiale.
Def. Un algoritmo risolve un problema in tempo pseudopolinomiale se esiste
un polinomio p() non decrescente tale che il tempo t(I) di decisione
dell'algoritmo sull'istanza I soddisfa t(I) ≤ p(n, m), con n = len(I) e m=max(I).
Sia Q è un problema di decisione; per ogni polinomio p'() indichiamo con Qp'
lo stesso problema ristretto alle istanze I aventi max(I) ≤ p'(len(I)).
Th. Se un algoritmo A risolve un problema Q in tempo pseudopolinomiale
allora risolve il problema Qp' in tempo polinomiale, per ogni polinomio p'().
Dim. Per ogni istanza I di Qp' si sa che tA(I) ≤ p(len(I), max(I)), per qualche
polinomio p() non decrescente. Ma max(I) ≤ p'(len(I)) e quindi tA(I) ≤
p(len(I), p'(len(I))) = q(len(I)), per qualche polinomio q().
Def. Un problema Q è un number-problem se non esiste alcun polinomio p'()
tale che max (I) ≤ p'(len(I)), per ogni istanza I di Q.
Th. Un problema Q che è NP-completo ma non un number-problem non può
essere risolto con un algoritmo pseudopolinomiale, a meno che P = NP.
Dim. Se Q non è un number problem esiste un polinomio p'() tale che max (I)
≤ p'(len(I)), per ogni istanza I di Q, e quindi Q = Qp' . Se Q fosse risolubile in
tempo pseudopolinomiale allora per il teorema precedente Qp ' lo sarebbe in
tempo polinomiale.
Def. Un problema NP-completo Q è NP-completo in senso forte se esiste un
polinomio p'() tale che il problema Qp' è NP-completo.
Th. Un problema NP-completo in senso forte Q non può essere risolto in
tempo pseudopolinomiale, a meno che P = NP.
Dim. Per qualche polinomio p'() si ha che il problema Qp' è NP-completo, non
è un number problem e quindi vale il teorema precedente.
KNAPSACK
Istanza: insieme fnito U; per ogni u ∈ U, due interi positivi: valore v(u) e
spazio s(u); interi positivi S, V.
Predicato: esiste un sottoinsieme U’ ⊆ U tale che:
∑u ∈ U' s(u) ≤ S e ∑u ∈ U' v(u) ≥ V?
Oss. KNAPSACK è NP-completo ed ovviamente è un number-problem.
Sappiamo che può essere risolto in tempo pseudopolinomiale.
Oss. KNAPSACK non è NP-completo in senso forte, a meno che P=NP.
Uno tra i più importanti risultati degli ultimi dieci anni
in teoria della trattabilità
La classe coNP è la classe di problemi il cui complemento appartiene alla
classe NP.
E’ facile mostrare che:
PRIMES ∈ coNP.
In effetti il suo complemento, COMPOSITES, è in NP in quanto si può
riconoscere (“certificare”) se un numero intero è composto indovinando non
deterministicamente un suo fattore.
Nel 1975 Vaughan Pratt dimostra che esiste un “certificato” per un numero
primo che può essere verificato in tempo polinomiale e mette quindi PRIMES
in NP ∩ coNP.
Ci sono voluti quasi 25 anni per dimostrare che:
PRIMES ∈ P
M. Agraval, N. Kayal, N. Saxena (2002)
© Copyright 2024 ExpyDoc
