E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 1

3 CENNI DI TEORIA DELLA

COMPLESSITA’ COMPUTAZIONALE

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 2

Scopo: Stimare l’onere computazionale per risolvere

problemi di ottimizzazione e di altra natura

• Determinare l’efficienza di un specifico algoritmo A

per risolvere un dato problema P

• Tentare di valutare la difficoltà intrinseca di un dato

problema P

Due tipi di obiettivi:

Particolare attenzione ai problemi di ottimizzazione

combinatoria

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 3

3.1 Complessità degli algoritmi

Definizione: Una istanza I di un problema P è un caso

specifico del problema.

Esempio Problema P : ordinare m numeri interi c1, ..., cm

Istanza I : m = 3, c1 = 2, c2 = 7, c3 = 5

Scopo: stimare l’onere computazionale di algoritmi

alternativi per risolvere un dato problema P al fine di

selezionare quello più efficiente

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 4

Chiaramente il numero di operazioni elementari dipende

dalla dimensione dell’istanza I

Tempo di calcolo valutato in termini di numero di

operazioni elementari ( aritmetiche, confronti, accessi

memoria,... ) necessarie per risolvere una data istanza I

Ipotesi: tutte le operazioni elementari richiedono

un’unità di tempo

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 5

Definizione: La dimensione di un’istanza I, indicata |I|,

è il numero di bit necessari a codificare (descrivere) I.

lo g iPoiché la codifica di un intero i richiede bit,

Esempio Istanza specificata dai valori di m e c1,..., cm

Per istanza m = 3, c1 = 2, c2 = 7, c3 = 5

|I| log 3 + 3 · log 7

Dimensione di una istanza

|I| log m + m · log cmax dove cmax= max{cj : 1 j m}

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 6

Per il problema di ordinamento di m interi Esempio

|I| log m + m · log cmax = O(log m + m log cmax )

Rapidità di crescita asintotica:

f(n) = O(g(n)) se c > 0 tale che f(n) c g(n)

per n sufficientemente grande

Si dice che f(n) è dell’ordine di g(n)

n0

c·g(n)

f (n)

n

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 7

Si cerca una funzione f (n) tale che, per ogni istanza I di

dimensione |I| n , il numero di operazioni elementari

per risolvere istanza I sia f (n)

Ordine di complessità

Esempio Per l’ordinamento di m interi esistono algoritmi

con complessità O(m log m)

Osservazioni:

• Poiché f (n) è un limite superiore I con |I| n, si

considera il caso peggiore

• f (n) espressa in termini di rapidità di crescita asintotica

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 8

Definizione: Un algoritmo è polinomiale se richiede,

nel caso peggiore, un numero di operazioni elementari

f(n) = O(nd) dove d è costante e n = |I| è la

dimensione dell’istanza.

O(nd)

polinomiale

O(2n)

esponenziale

Si distinguono algoritmi con ordini di complessità:

Un algoritmo in O(n7) non è efficiente in pratica!

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 9

• Algoritmo di Dijkstra per problema dei cammini minimi

Dimensione di una istanza: |I| = O(m log n + m log cmax)

Complessità: O(n2) dove n è il numero di nodi

• Versione di base dell’algoritmo di Ford-Fulkerson per

problema di flusso massimo

Esempi

Dimensione di una istanza: |I| = O(m log n + m log kmax)

Complessità: O(m2 kmax) dove m è il numero di archi

Rapidità di crescita polinomiale rispetto a |I| (|I| ≥ m ≥ n -1)

Rapidità di crescita non polinomiale rispetto a |I|

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 10

3.2 Complessità dei problemi

Scopo: stimare la difficoltà intrinseca di un problema per

adottare l’approccio risolutivo più adeguato

Intuitivamente, la difficoltà intrinseca corrisponde alla

complessità del migliore “possibile” algoritmo!

Definizione: Un problema P è polinomiale ( “facile” ) se

esiste un algoritmo polinomiale che fornisce una soluzione

(ottima) per ogni istanza.

Esempi: cammini minimi, flussi di valore massimo,...

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 11

? Esistono problemi “difficili”?

Per molti problemi di ottimizzazione i migliori

algoritmi noti tutt’oggi richiedono un numero di

operazioni elementari che cresce, nel caso peggiore,

esponenzialmente con la dimensione dell’istanza

N.B.: Non dimostra che sono effettivamente “difficili”!

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 12

Problema del commesso viaggiatore

Problema

“Travelling Salesman Problem”

(TSP)

Un commesso viaggiatore deve visitare ciascuna di n città

esattamente una volta e ritornare al punto di partenza nel minor

tempo possibile.

Dato G = (N, A) orientato con un costo cij per

ogni (i, j) A, determinare un circuito di costo

minimo che visita esattamente una volta ogni nodo.

Z

collegamenti con tempi

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 13

Definizione: Un circuito C è hamiltoniano se passa

esattamente una volta per ogni nodo.

Indicando con H l’insieme di tutti i circuiti hamiltoniani

di G, il problema equivale a

( , )

m ini j

C Hi j C

c

Applicazioni: distribuzione, sequenziamento ottimo, VLSI,…

| H | ( n – 1 )! H contiene un numero finito di elementi:

Numerose varianti ed estensioni (Vehicle Routing Problem --VRP)

14 http://www.tsp.gatech.edu

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 15

Ad ogni problema di ottimizzazione viene associata una

versione di riconoscimento

Esempio TSP-r

Dato G = (N, A) con distanze cij intere e un intero L, esiste

un circuito hamiltoniano di lunghezza L ?

Si fa riferimento ai problemi di riconoscimento e non a

quelli di ottimizzazione

3.3 Teoria della NP-completezza

Definizione: Un problema di riconoscimento è un

problema che richiede una risposta “si”/“no”

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 16

Qualsiasi problema di ottimizzazione è almeno

altrettanto difficile della sua versione di riconoscimento

Se versione di riconoscimento è difficile

il problema di ottimizzazione è anch’esso difficile

Problemi di riconoscimento

Se si riesce a individuare un circuito hamiltoniano di

lunghezza minima si può chiaramente rispondere alla

domanda di TSP-r (ne esiste uno di lunghezza L?)

Esempio

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 17

Definizione: P indica l’insieme dei problemi di

riconoscimento che si possono risolvere in tempo polinomiale.

Esempi: quelli associati ai problemi di alberi ottimi, di cammini

minimi e di flussi massimi

Classe di complessità P

Per ciascuno di essi esiste un algoritmo che permette di

stabilire per ogni istanza I se la risposta è “si” o “no” in

tempo polinomiale in |I|

Definizione formale di P in termini di macchina di Turing

(deterministica) polinomiale

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 18

Classe di complessità NP

Definizione: NP indica l’insieme dei problemi di

riconoscimento tali che per ogni istanza con risposta “si”

esiste una prova concisa (certificato) che permette di

verificare in tempo polinomiale che la risposta è “si”.

TSP-r poiché si può verificare in tempo polinomiale

se una sequenza di nodi è un circuito hamiltoniano e

se lunghezza L

Esempio

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 19

N.B.: Non importa quanto è difficile ottenere il certificato (può

essere fornito da un “oracolo”) basta che esista e sia

verificabile in tempo polinomiale!

NP indica l’insieme dei problemi di riconoscimento per i quali

un polinomio p(n) e un algoritmo di verifica del certificato Avc tale che :

istanza I ha risposta “si” un certificato (I) di dimensione

polinomiale (| (I)| p(|I|) ) e Avc applicato all’input “I, (I)” da

risposta “si” in un numero di operazioni elementari ≤ p(|I|).

Definizione formale:

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 20

Chiaramente P NP

Congettura P NP

P

NP

P

!

NP non sta per “Non Polinomiale” ma per “Non-

deterministico Polinomiale” (fa riferimento alle

macchine di Turing non-deterministiche polinomiali)

Uno dei “Millennium Prize

Problems” 2000!

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 21

Concetto di riduzione polinomiale permette di confrontare i

problemi di riconoscimento ed individuare quelli più difficili

Riduzione polinomiale tra problemi

Definizione:

Sia P1 e P2 NP, P1 si riduce in tempo polinomiale a P2

(P1 P2) se esiste un algoritmo per risolvere P1 che

• chiama un certo numero di volte un ipotetico algoritmo

per P2 ,

• e risulta polinomiale se si suppone che quello per P2

richieda un’unica unità di tempo.

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 22

Esempio

Caso più semplice: l’algoritmo per P2 viene chiamato

un’unica volta.

P2: Dato un grafo orientato G’ = ( N’, A’) con costi e un intero L’, ∃ un circuito hamiltoniano di lunghezza L’ ?

P1: Dato un grafo non orientato G = ( N, E ) con costi e un intero L, ∃ un ciclo hamiltoniano di lunghezza L?

P1 P2

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 23

in tempo e spazio polinomiale

I1 P1 è facile costruire una particolare I2 P2

tale che I1 ha risposta “si” I2 ha la risposta “si”

Riduzione polinomiale dal caso non orientato a quello

orientato :

1 1

5

2

3

4

2 2

6

5

3

4

4 2 G=(N,E)

1

5

2

3

4

1

2 2

6

5

3

4

4 2 G’=(N’,A’)

L = 15 L’ = 15

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 24

Conseguenza:

Se P1 P2 e P2 è risolubile mediante un algoritmo

polinomiale, allora anche P1 può essere risolto in

tempo polinomiale.

P2 P P1 P

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 25

Definizione: Un problema P è NP-completo se e solo se

1) appartiene a NP

2) ogni altro problema in NP è riducibile ad esso

in tempo polinomiale ( P’ P , P’ NP )

NP

P

NP-completi

Problemi NP-completi

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 26

Proprietà: Se un problema NP-completo P fosse risolubile

in tempo polinomiale (se P ), allora lo sarebbero tutti i

problemi di NP, cioè si avrebbe P =NP !!

eventualità considerata estremamente improbabile

La NP-completezza è quindi un forte indizio di difficoltà

intrinseca

cf. lunga lista di problemi di riconoscimento importanti che risultano

NP-completi e per i quali non sono noti algoritmi polinomiali

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 27

Esistono problemi NP-completi?

assegnamento: y1 = vero, y2 = falso, y3 = falso

Soddisfacibilità (SAT)

Date m clausole booleane C1,…, Cm ( disgiunzioni --

OR -- di variabili booleane yj e loro complementi yj ),

esiste un assegnamento di valori “vero” o ”falso” alle

variabili che rende vere tutte le clausole?

¯

Esempio C1 : ( y1 y2 y3 )

C2 : ( y1 y2 )

C3 : ( y2 y3 )

¯

¯

¯

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 28

Primo problema dimostrato NP-completo:

Teorema (Cook 1971)

SAT è NP-completo

Stephen A.Cook 1939-

Tramite i concetti di macchina di Turing e riduzione polinomiale

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 29

Mostra che le versioni di riconoscimento di 21 problemi

di ottimizzazione combinatoria sono NP-completi

(1974)

Richard M. Karp 1935-

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 30

Per stabilire che P2 NP è NP-completo “basta” mostrare

che un problema NP-completo P1 si riduce polinomialmente

a P2 :

P P1, P NP , e P1 P2 implica per transitività che

P P2 , P NP

P1: Dato G non orientato con costi e un intero L, ∃ un

ciclo hamiltoniano di lunghezza L?

P2: Dato G’ orientato con costi e un intero L’, ∃ un circuito

hamiltoniano di lunghezza L’ ?

Esempio

Come mostrare la NP-completezza?

P2 NP e P1 P2 con P1 NP-completo

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 31

• Dato G = (N, E) non orientato, esiste un ciclo

hamiltoniano? (Karp 74)

• Dato un sistema lineare A x b con coefficienti interi,

esiste una soluzione x con componenti 0-1?

• ….

Esempi di problemi NP-completi

• Dato G = (N, A) orientato, due nodi assegnati s e t, e un

intero L, esiste un cammino semplice (con nodi distinti)

da s a t che contiene un numero di archi L?

• Dato G = (N, A) orientato con costi sugli archi, due

nodi s e t, e un intero L, esiste un cammino semplice

da s a t di costo L?

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 32

Definizione: Un problema è NP-difficile se ogni problema

in NP è riducibile ad esso in tempo polinomiale (anche se

non appartiene ad NP )

Esempio TSP poiché TSP-r (esiste un circuito hamiltoniano

di lunghezza L?) è NP-completo.

Problemi NP-difficili

Tutti i problemi di otttimizzazione di cui la versione di

riconoscimento è NP-completa sono NP-difficili.

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 33

1) Verificare che la versione di riconoscimento del caso

binario, r-PL0-1, appartiene a NP .

r-PL0-1: Dato A x b con coefficienti interi, esiste una

soluzione x {0, 1}n?

2) Mostrare che SAT (NP-completo) si riduce

polinomialmente a r-PL0-1. (cf. esercizio 3.3)

Programmazione Lineare Intera (PLI):

Dati A m n, b m 1 e c n 1 con coefficienti interi, trovare

x con componenti intere tale che Ax b e minimizza cTx.

Proposizione (Karp 74): PLI è NP-difficile.

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 34

• Dati matrice A m n, e vettori b m 1 e c n 1 con

componenti intere, trovare un x {0, 1}n che soddisfi

Ax b e minimizzi cTx.

• ….

Esempi di problemi NP-difficili

• Dato G = (N, A) orientato con costi sugli archi, due nodi

assegnati s e t, determinare un cammino semplice di

costo massimo tra s e t.

• Dato G = (N, A) orientato con costi sugli archi, due

nodi s e t, determinare un cammino semplice di costo

minimo tra s e t.

E. Amaldi – Fondamenti di R.O. – Politecnico di Milano 35

Qual è la dimensione di un’istanza del problema

dell’albero di supporto di costo minimo? Esercizio