Giuseppe Bruno » 5.Fondamenti di teoria della complessità computazionale

Argomenti della lezione

• Alcune definizioni fondamentali
• Complessità di un algoritmo
• Problemi trattabili e problemi intrattabili
• Problemi decisionali
• Problemi P ed NP
• I problemi NP-hard

Alcune definizioni fondamentali

In termini generali un problema di ottimizzazione può essere formulato come

z = f (x)   Max!
x ∈ X

con

• X di insieme di soluzioni ammissibili
• z=f(x) funzione obiettivo z=f(x) da massimizzare

Una soluzione x*∈X è un massimo locale se f(x*)≥f(x) per ogni x ∈Iε(x).

Una soluzione x*∈X è un massimo globale se f(x*)≥f(x) per ogni x ∈X.

Alcune definizioni fondamentali (segue)

Per definire un problema di ottimizzazione è necessario individuare:

• un insieme X di soluzioni ammissibili
• una funzione obiettivo z=f(x) da massimizzare definita per ogni x∈X che rappresenta il criterio di valutazione.

Una soluzione x*∈X è un massimo (minimo) locale se f(x*)≥f(x)
(f(x*)≤f(x)) per ogni x ∈Iε(x).

Una soluzione x*∈X è un massimo (minimo) globale se f(x*) ≥f(x)
(f(x*)≤f(x)) per ogni x ∈X.

Alcune definizioni fondamentali (segue)

Problema e metodo di risoluzione

Una volta formalizzato un problema di ottimizzazione si pone il problema di individuarne le soluzioni (ottimi globali o locali).

Un metodo di risoluzione è una tecnica che consente di trovare soluzioni del problema.

Un metodo di risoluzione può essere

• esatto se individua un ottimo globale ammissibile;
• euristico se è orientato alla ricerca di una buona soluzione (ma non necessariamente ottima).

Alcune definizioni fondamentali (segue)

Istanza e dimensione di un problema

Un’istanza di un problema rappresenta un esempio del problema in esame

Dato un problema Π, si dice che un’istanza I di Π ha dimensione n, nell’alfabeto (finito) Σ, se la sequenza di simboli di Σ necessaria per codificare i dati di ingresso richiede n simboli.

Un alfabeto classicamente adottato per la codifica è l’alfabeto binario (Σ={0,1}); in questo caso la dimensione di I è pari al numero di bit necessari per la codifica dei dati di input.

Complessità di un algoritmo

Funzione di complessità di un algoritmo f(n)

Rappresenta, per ogni possibile valore n della dimensione del problema, il massimo numero di operazioni necessario all’algorimo a risolvere un problema di dimensione n.

Un algoritmo è di tipo polinomiale se la sua funzione di complessità f(n)=O(n^k).

Ogni algoritmo la cui funzione di complessità non è polinomiale è detto di tipo esponenziale.

Problemi trattabili ed intrattabili

Un problema si dice trattabile se esiste un algoritmo polinomiale in grado di risolverlo.

In caso contrario, ovvero se non può esistere un algoritmo polinomiale in grado di risolverlo, si dice intrattabile.

La ragione di questa distinzione risulta evidente dalla tabella fornita da Garey and Johnson (1979).

Problemi trattabili ed intrattabili (segue)

Problemi decisionali

La teoria della complessità computazionale o della “NP completezza” (NP-Completeness) punta ad un’ulteriore classificazione dei problemi facendo riferimento ai cosiddetti problemi decisionali.

Un problema decisionale è un problema formulato in modo da ammettere due sole possibili risposte: SI o NO.

Esempio:
Dato un numero intero K, esiste una coppia di numeri interi m ed n (con m,n>1) tali che K=mn ?

Problemi decisionali (segue)

Ogni problema di ottimizzazione può essere formulato come problema decisionale.

Esempio del problema del commesso viaggiatore (TSP)

Problema di ottimizzazione del TSP
Date n città, si individui il circuito di lunghezza minima che un commesso viaggiatore deve effettuare per visitare ciascuna città una sola volta.

Problema decisionale del TSP
Date n città, esiste un circuito che un commesso viaggiatore può effettuare per visitare ciascuna città una sola volta che risulti di lunghezza non superiore ad un valore B (≤B)?

Poiché per risolvere un problema di ottimizzazione si devono risolvere più problemi di decisione ad esso associati, si può concludere che la complessità di un problema di ottimizzazione sarà almeno pari a quello del problema di decisione ad esso associato.

Problemi P ed NP

Un problema decisionale è di tipo P se esiste un algoritmo polinomiale in grado di fornire una risposta di tipo SI o NO, ossia se è trattabile.

Un problema decisionale è di tipo NP se esiste un algoritmo polinomiale in grado di verificare una risposta di tipo SI.

Differenza tra P ed NP
Mentre in un problema P bisogna trovare la risposta in tempo polinomiale, in un problema NP, nel caso ci venga fornita una risposta di tipo SI, bisogna verificare che la risposta fornita sia effettivamente di tipo SI in tempo polinomale.

Ad esempio il TSP non è un problema di tipo P perché non siamo in grado di fornire una risposta in tempo polinomiale. Tuttavia il TSP è di tipo NP, perché, dato un circuito hamiltoniano di lunghezza ≤B, è possible verificare che si tratta di un circuito hamiltoniano di lunghezza ≤B in tempo polinomiale,

NP completezza

All’interno della classe dei problemi NP è possibile individuare un sottoinsieme di problemi “più difficili” detti NP-completi.

A tal fine è necessario introdurre il concetto di riducibilità tra due problemi.

Un problema Π è riducibile ad un problema Π* (Π ∝ Π*) se ogni istanza di Π può essere trasformato in tempo polinomiale in un’istanza di Π*.

Sia Π ∝Π *
↓

• se Π* è di tipo P allora anche Π è di tipo P
• se Π* non è di tipo P allora anche Π non è di tipo P

NP completezza (segue)

NP completezza (segue)

NP completezza (segue)

NP completezza (segue)

NP completezza (segue)

NP completezza (segue)

Importanza della classe dei problemi NP-completi

La classe dei problemi NP-completi è una classe di problemi più difficili all’interno della classe NP.

Se si individuasse un algoritmo polinomiale per risolvere un qualsiasi problema NP-completo allora tutti i problemi NP sarebbero trattabili ovvero P=NP.

Se si dimostrasse che un problema NP-completo è intrattabile, allora tutti i problemi NP sarebbero intrattabili ovvero P≠NP.

Un problema di ottimizzazione la cui versione decisionale appartiene alla classe dei problemi NP-completi è detto NP-hard (NP-difficile).

Conclusioni

La teoria della NP-completezza consente di classificare nella classe dei problemi NP e NP-completo, problemi che non risultano né trattabili, né intrattabili.

Anche se non è stato dimostrato formalmente si adotta la congettura (l’ipotesi) P≠NP, ovvero si ritiene che i problemi NP siano intrattabili.

Ne consegue che i problemi NP vanno trattati, in pratica, come se fossero intrattabili. Pertanto poiché i tempi di calcolo di algoritmi risolutivi esatti applicati a questi problemi risultano esponenziali, nelle applicazioni pratiche bisogna ricorrere ad algoritmi di risoluzione euristici.