E bene osservare che nella definizione precedente il criterio logaritmico non pu`o essere sostituito con quello uniforme. Infatti i due criteri possono fornire valutazioni molto diverse fra loro, anche se per molti programmi RAM i corrispondenti tempi di calcolo sono polinomialmente legati tra loro. In particolare, `e abbastanza facile descrivere programmi RAM che, su un input x, richiedono un tempo lineare in |x| secondo il criterio uniforme e uno esponenziale secondo quello logaritmico. Abbiamo gi`a incontrato un programma di questo genere nell’esempio 3.3.
13.3 La classe NP
Ricordiamo che un problema di ottimizzazione pu`o essere definito nel modo seguente: dato un insieme di elementi E, una famiglia F ⊆ 2E di soluzioni ammissibili e una funzione peso w : E −→ IN, determinare una soluzione ammissibile di peso massimo. La risposta in questo caso non `e binaria (“si” o “no”), quindi il problema cos`ı formulato non `e un problema di decisione. `E per`o possibile ottenere facilmente una versione di decisione introducendo nell’istanza del problema un intero k: la questione diventa quella di decidere se esiste una soluzione ammissibile di peso almeno k.
Esempio 13.1
Consideriamo il problema di ottimizzazione MAX CLIQUE cos`ı definito MAX CLIQUE
Istanza: un grafo non orientato G = hV, Ei.
Soluzione ammissibili: le clique di G, cio`e i sottoinsiemi C ⊆ V tali che {v, w} ∈ E per ogni coppia di nodi distinti v, w ∈ C.
Peso di una soluzione: il numero dei suoi elementi. Questione: determinare la clique di peso massimo in G. La versione di decisione di tale problema `e invece la seguente:
CLIQUE
Istanza: un grafo non orientato G = hV, Ei e un intero k, 0 ≤ k ≤ ]V . Domanda: esiste una clique di peso almeno k in G?
1. `E computazionalmente costoso in generale determinare la soluzione ammissibile di peso almeno k mediante l’algoritmo esaustivo; questo `e dovuto al fatto che le soluzioni ammissibili sono spesso dell’ordine di 2n, dove n `e la dimensione dell’istanza. Per molti di tali problemi, inoltre, non `e stato trovato alcun algoritmo risolutivo che lavori in tempo polinomiale.
2. `E invece computazionalmente facile verificare se un certo insieme di elementi `e una soluzione ammissibile di peso almeno k; questo significa che, se una istanza ammette risposta positiva, esiste una soluzione ammissibile che “dimostra” (o “testimonia”) la validit`a della risposta mediante una facile verifica.
La classe NP raggruppa problemi che hanno le caratteristiche sopra descritte. Esso contiene molti problemi che sono la versione di decisione di problemi di ottimizzazione (sia di massimo che di min-imo) insieme ad altri che richiedono pi`u semplicemente di verificare l’esistenza di una soluzione con certe caratteristiche. Si tratta di problemi per i quali non sono noti algoritmi che funzionano in tempo polinomiale, ma per i quali si pu`o facilmente verificare se una certa soluzione candidata `e effettivamente soluzione di una data istanza.
Prima di fornire la definizione formale, ricordiamo che, dati due insiemi di istanze I e J , una re-lazione R ⊆ I × J si dice riconoscibile da una RAM M se, su input (i, j) ∈ I × J , M verifica se (i, j) appartiene a R. Si assume che la dimensione dell’input (i, j) sia la somma delle dimensioni di i e j; nel caso del criterio di costo logaritmico essa equivale al numero di bit necessari per rappresentare i due elementi.
Definizione 13.1 Un problema di decisione Π = hI, qi appartiene alla classe NP se esistono un insieme
∆ di elementi (potenziali “dimostrazioni”), una relazione R ⊆ I × ∆ riconoscibile da una RAM in
tempo polinomiale (secondo il criterio logaritmico) e un polinomio p tali che per ogni istanza x ∈ I: 1. se q(x) = 1 allora esiste D ∈ ∆ tale che |D| ≤ p(|x|) e inoltre (x, D) ∈ R;
2. se q(x) = 0 allora per ogni D ∈ ∆ si verifica (x, D) 6∈ R.
Osserva che se (x, D) ∈ R, D pu`o essere considerato come “testimone” o “dimostrazione” del fatto che x rende vera q.
Vediamo alcuni esempi di problemi in NP. Il primo `e il problema CLIQUE che abbiamo gi`a incontrato in un esempio precedente:
CLIQUE
Istanza: un grafo non orientato G = hV, Ei e un intero k, 0 ≤ k ≤ ]V . Domanda: esiste una clique di peso almeno k in G?
In questo caso la “dimostrazione” che un grafo G ha una clique di dimensione k `e semplicemente un sottoinsieme D di vertici di G contenente k elementi: si pu`o facilmente verificare in tempo polinomiale se D `e proprio una clique di G.
Un altro problema di carattere combinatorio appartenente alla classe NP `e il seguente: CIRCUITO HAMILTONIANO
Istanza: un grafo G = hV, Ei non orientato.
Domanda: esiste in G un circuito hamiltoniano, ovvero una permutazione (v1, v2, . . . , vn) dei nodi del grafo tale che {vi, vi+1} ∈ E per ogni i = 1, . . . , n−1, e inoltre {vn, v1} ∈ E?
Qui la “dimostrazione” che G possiede un circuito hamiltoniamo `e una permutazione D dei nodi del grafo; anche in questo caso si pu`o verificare in tempo polinomiale se D `e effettivamente un circuito hamiltoniano di G.
Un altro rilevante problema in NP `e quello della soddisfacibilit`a per formule booleane in forma normale congiunta. Per definire tale problema ricordiamo innanzitutto che una formula booleana `e un letterale, cio`e una variabile x o una variabile negata x, oppure una delle seguenti espressioni:
(i) (¬φ),
(ii) φ1∧ φ2∧ · · · ∧ φk, (iii) (φ1∨ φ2∨ · · · ∨ φk),
dove k ≥ 2, mentre φ, φ1, φ2, . . . , φk sono formule booleane. Di solito si rappresentano con i simboli di somma e prodotto le tradizionali operazioni booleane ∨ e ∧. Ogni formula booleana nella quale compaiono k variabili distinte definisce in modo ovvio una funzione f : {0, 1}k −→ {0, 1}. Diciamo che una formula booleana φ `e in forma normale congiunta (FNC per brevit`a) se φ `e un prodotto di clausole di letterali, ovvero
φ = E1· E2· . . . · Ek (13.1) dove Ei = (`i1+ `i2+ · · · + `iti) per ogni i = 1, 2, . . . , k, e ciascun `ij `e un letterale. Un esempio di formula booleana in FNC `e dato dall’espressione
U (y1, y2, . . . , yk) = ( k X i=1 yi) ·Y i6=j (yi+ yj). (13.2) `
E evidente che U (y1, y2, . . . , yk) vale 1 se e solo se esattamente una delle sue variabili yi assume valore 1.
Allora il problema della soddisfacibilit`a per tali formule pu`o essere definito nel modo seguente: SODD
Istanza: una formula φ in forma normale congiunta su un insieme di variabili x1, x2, . . . , xm.
Domanda: esiste un assegnamento di valori alle variabili, cio`e un funzione A : {x1, x2, . . . , xm} −→ {0, 1}, che rende vera φ?
Anche in questo caso la dimostrazione `e proprio un assegnamento A di valori alle variabili di φ. Dato A si verifica in tempo polinomiale se A sende vera la φ.
Un problema che sorge ora in modo naturale `e quello di confrontare le classi P e NP appena definite. Si verifica facilmente la seguente
Proposizione 13.1 La classe P `e contenuta in NP
Dimostrazione. Infatti, se un problema di decisione Π = hI, qi appartiene a P `e sufficiente definire l’insieme ∆ = {1} e porre R = {(x, 1) | x ∈ I, q(x) = 1}. Cos`ı lo stesso algoritmo che risolve Π in tempo polinomiale di fatto riconosce la relazione R in un tempo analogo, mentre le propriet`a 1) e 2) della definizione 13.1 sono banalmente verificate.
Si verifica inoltre che ogni problema in NP pu`o essere risolto in tempo esponenziale.
Proposizione 13.2 Ogni problema in NP pu`o essere risolto da una RAM in tempo O(2f (n)) secondo il
criterio logaritmico, per qualche polinomio f (x).
Dimostrazione. Sia π = hI, qi un problema in NP; allora esistono un insieme di “dimostrazioni” ∆, una relazione R e un polinomio p che soddisfano le condizioni poste dalla definizione 13.1. Sia inoltre M la RAM che riconosce R in un tempo polinomiale r(n). Possiamo allora definire una nuova RAM M0che su input x ∈ I calcola tutte le “dimostrazioni” D ∈ ∆ di dimensione minore o uguale a p(|x|) e, per ognuna di queste, verifica se (x, D) appartiene a R simulando la macchina M . Quindi M0restituisce il valore 1 se (x, D) appartiene a R per qualche D tra quelle considerate, mentre restituisce il valore 0 altrimenti.
Chiaramente M0 risolve il problema π. Inoltre, se n `e la dimensione di x, vi sono al pi`u 2p(n) “dimostrazioni” D di dimensione p(n). Per ognuna di queste la verifica se (x, D) appartiene a R si esegue in tempo r(n). Di conseguenza anche il tempo complessivo risulta O(2f (n)), dove f (n) `e un polinomio tale che f (n) = O(p(n) + r(n)) .
Esercizio
Dimostrare che il seguente problema appartiene a NP: COMMESSO VIAGGIATORE
Istanza: un intero k > 0, un grafo diretto G = hV, Ei e una funzione peso d : E → IN. Domanda: esiste un circuito che congiunge tutti i nodi del grafo di peso minore o uguale a k, ovvero una permutazione (v1, v2, . . . , vn) di V tale chePi=1n−1d(vi, vi+1) + d(vn, v1) ≤ k?