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 Aper risolvere un dato problema P

• Tentare di valutare la difficoltà intrinseca di un dato problema P

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

3.1 Complessità degli algoritmi

Un’istanza I di un problema P è un caso specifico del problema

Esempio Problema P: ordinare n numeri interi c1, ..., cn

Istanza I : n = 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

Principali risorse⎧⎨⎩

tempo di calcolo

spazio di memoria

Chiaramente il numero di operazioni elementari dipende dall’istanza I

Facendo riferimento ad un modello di calcolo astratto come la macchina di Turing, si considera il numero di operazioni elementari ( aritmetiche, confronti,... ) necessarie per risolvere una data istanza I

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

La dimensione di un’istanza I, indicata |I|, è il numero di bit necessari a codificare (descrivere) I

Esempio

log i⎡ ⎤⎢ ⎥Poiché la codifica di un intero i richiede bit,

Istanza specificata dai valori di n e c1, ..., cn

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

⇒ ⎡log 3⎤ + 3 · ⎡log 7⎤

Dimensione di un’istanza

log logn n c⋅+⎡ ⎤ ⎡ ⎤⎢ ⎥ ⎢ ⎥ dove1max i

i nc c

≤ ≤=|I| =

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

In genere, si considera la rapidità di crescita del numero di operazioni elementari (o.e.) nel caso peggiore :

numero di o.e. per risolvere istanza I ≤ f (n) ∀I con |I| ≤ n

Complessità 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)

Ordine di complessità

n0

c·g(n)f (n)

n

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

Un algoritmo è polinomiale se richiede, nel caso peggiore, un numero di operazioni elementari

f(n) = O(nd) con n = |I| e d costante.

O(nd)polinomiale

O(2n)esponenziale

Si distinguono algoritmi con:

Gli algoritmi polinomiali sono in genere considerati efficienti anche se uno in O(n10) non lo è molto in pratica!

Esempio Per l’ordinamento di n interi esiste un algoritmoO(n log n)

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

• Algoritmi di Prim (alberi ottimi) e di Dijkstra (cammini minimi) complessità polinomiale: O(n2)

• Versione di base dell’algoritmo di Ford – FulkersonRicerca cammino aumentante: O(m)

Valore flusso massimo ϕ* ≤ m kmax kmax= max{kij: (i,j) ∈A}

Se kij intere, il valore ϕ aumenta di almeno δ = 1 unità ad ogni iterazione Partendo dal flusso di valore x = 0 con ϕ0 = 0, si ha quindi una complessità totale O(m2 kmax)

Esempi

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

N.B.: la dimensione di un’istanza è O(m log kmax) perché la capacità di ogni arco può essere codificata su ⎡log kmax⎤ bit

Modifica che lo rende polinomiale:cercare cammino aumentante con un numero minimodi archi( Edmonds e Karp O(nm2), Dinic O(n2m), e Malhorta, Kumar e Maheshwari O(n3) )

maxlogmax 2 kk =Poiché l’ordine di complessità totale

O(m2 kmax) non è polinomiale rispetto alla dimensione!

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

3.2 Complessità dei problemi

Scopo: stimare la difficoltà intrinseca di un problema (che corrisponde alla complessità del “miglior algoritmo che permetterebbe di risolverlo”) per adottare l’approccio risolutivo più adeguato

Un problema P è polinomiale ( “facile” ) se esiste un algoritmo polinomiale che fornisce la 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

“TravellingSalesman Problem” TSP

Un commesso viaggiatore deve visitare ciascuna di ncittà esattamente una volta e ritornare al punto di partenza nel minor tempo possibile.

Dato un grafo orientato G = (N, A), con un costo cij ∈ , ∀ (i, j) ∈ A, determinare un circuito di costo minimo che visita esattamente una voltaogni nodo.

Z

collegamenti con tempi

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

Un circuito C è hamiltoniano se passa esattamente una volta per ogni nodo.

Indicando con H l’insieme di tutti i circuiti hamiltonianidi G, il problema equivale a

( , )

min ijC H i j C

c∈

∈∑

Applicazioni: distribuzione, sequenziamento ottimo, VLSI, …

| H | ≤ ( n – 1 )!

N.B.: H contiene un numero finito di elementi

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

Ad ogni problema di ottimizzazione viene associata una versione di riconoscimento

Esempio TSP-r

Dato un grafo orientato G = (N, A) con distanze cijintere e un intero L, esiste un circuito hamiltonianodi lunghezza ≤ L ?

Non si fa direttamente riferimento ai problemi di ottimizzazione ma ai problemi di riconoscimento( risposta “si” / “no” )

3.3 Teoria della NP-completezza

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

Qualsiasi problema di ottimizzazione è almeno altrettanto difficile della sua versione 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?)

Se versione di riconoscimento è difficile

⇒ il problema di ottimizzazione è anch’esso difficile

Problemi di riconoscimento

Esempio

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

P indica la classe dei problemi di riconoscimento che si possono risolvere in tempo polinomiale.

Esempi: quelli associati ai problemi di alberi ottimi, di camminiminimi 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 17

Esempio: TSP-r poiché si può verificare in tempo polinomiale se una sequenza di nodi è un circuitohamiltoniano e se lunghezza ≤ L

Classe di complessità NP

Si richiede solo che per ogni istanza con risposta “si”esista una prova concisa (certificato) che permetta di verificare in tempo polinomiale che la risposta è “si”.

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

NB: Non importa quanto è difficile ottenere ilcertificato (può essere fornito da un “oracolo”) basta

che esista e sia verificabile in tempo polinomiale!

NP indica la classe dei problemi di riconoscimentoper 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 applicatoall’input “I,γ(I)” da risposta “si” in un numero dioperazioni elementari ≤ p(|I|).

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

Chiaramente P ⊆ NP

Congettura P ⊂ NP

P

NP

P

!NP non sta per “Non Polinomiale” ma per “Non-deterministico Polinomiale” (fa riferimento allemacchine di Turing non-deterministiche polinomiali)

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

Per confrontare i problemi di riconoscimento e definire quelli più difficili si utilizza il concetto di riduzione polinomiale.

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 P2richieda un’unica unità di tempo.

Riduzione polinomiale fra problemi

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

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 22

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 :

11

5

2

3

4

226

5

34

42G=(N,E)

1

5

2

3

4

1

226

5

34

42G’=(N’,A’)

L = 15 L’ = 15

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

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 24

Un problema P è NP-completo se e solo se1) appartiene a NP2) ogni altro problema in NP è riducibile ad esso

in tempo polinomiale ( P’ ∝ P , ∀ P’ ∈ NP )

NPP

NP-completi

Problemi NP-completi

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

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 estremamenteimprobabile

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

cf. lunga lista di problemi NP-completi per i quali non sono noti algoritmi polinomiali

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

Primo problema dimostrato NP-completo (Cook 1971) :

Esempio

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?

¯

C1 : ( y1 ∨ y2 ∨ y3 )C2 : ( y1 ∨ y2 ) C3 : ( y2 ∨ y3 )

¯¯¯

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

Per stabilire che P2 ∈ NP è NP-completo “basta”mostrare che un altro 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 28

• Dato G = (N, E) non orientato, ciclo hamiltoniano ?

• Dato un sistema lineare A x ≥ b con coefficienti interi, esiste una soluzione x a valori 0, 1 ?

• ….

Altri 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 sempliceda s a t di costo ≤ L ?

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

Un problema è NP-difficile se ogni problema in NPè riducibile ad esso in tempo polinomiale (anche se non appartiene ad NP)

EsempioTSP poiché TSP-r (esiste un circuito hamiltonianodi 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 30

• 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.

• ….

Altri 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 31

Qual è la dimensione di un’istanza del problema dell’albero di supporto di costo minimo ?

Esercizio

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

Suggerimento: procedere per riduzione dal problemadi soddisfacibilità (SAT)

Programmazione Lineare Intera (PLI):

Dati A, b e c interi, trovare un x a valori 0, 1 che soddisfa Ax ≥ b e minimizza cTx.

Verificare che la programmazione lineare interaè un problema NP-difficile.Esercizio