ARP

COMPLESSITA'

1-EFFICIENZA E POLINOMIALITA'

EFFICIENZA = utilizzazione intelligente di risorse scarse e/o costose

RISORSE: spazio di memoria, numero di processori, banda di comunicazione, tempo di calcolo

DIMENSIONE DEI DATI (DI UN' ISTANZA) DI UN PROBLEMA = numero n di bit necessario per fornirli al calcolatore

NOTA: le risorse di cui sopra sono dette risorse dinamiche perché dipendono dal valore di n. Altre risorse (statiche) che non ne dipendono non ci interessano. Quasi sempre ci limiteremo a considerare solo il tempo di calcolo e/o (più raramente) lo spazio di memoria. Le altre risorse interessano solo nel caso di macchine parallele.

DEFINIZIONE   f(n) = O(g(n)) (si legge "f di n è ordine di g di n") se esiste c>0 tale che

f(n) c g(n)

per n sufficientemente grande.

DEFINIZIONE   Se il tempo di calcolo di un algoritmo A per un problema P è O(n^k) con k indipendente da n, diciamo che A risolve P in tempo polinomiale.

NOTA: molti problemi di PLI sono "finiti" nel senso che ammettono solo un numero finito di soluzioni ammissibili. Il metodo semplicistico di enumerarle tutte per scegliere la migliore porta a tempi di calcolo proibitivi anche per i calcolatori più potenti oggi immaginabili (salvo modelli di calcolo astratti e non realizzabili).

Ad esempio in un grafo di n nodi il numero di alberi diversi può arrivare a n^n-2, nel problema di assegnamento ci sarebbero n! soluzioni diverse, e così via. Un criterio universalmente accettato, anche se molto grossolano, afferma che un problema è ben risolto quando si dispone di un algoritmo polinomiale per la sua soluzione. Ciò vale solo per alcuni (importanti) problemi ed è molto probabile che sia sempre così.

Gran parte del corso è dedicata a vedere cosa fare di fronte a questa situazione. 

2-COMPLESSITA' DEI PROBLEMI

A. PROBLEMI BEN RISOLTI (cioè polinomiali)

Albero minimo

Accoppiamento ottimo

Cammini minimi

Flusso massimo di costo minimo

PLI con vincoli TUM

B. PROBLEMI DIFFICILI

Zaino binario

Copertura di insiemi

Commesso Viaggiatore

PLI in generale

Albero di Steiner

DA OTTIMIZZAZIONE A RICONOSCIMENTO

Dal problema max otteniamo il problema di riconoscimento:

"esiste un xIF tale che c^Tx k ?"

DEFINIZIONE   NP è la classe di problemi di riconoscimento con la seguente proprietà: per ogni istanza del problema con risposta SI esiste una dimostrazione "efficiente" (cioè polinomiale) che tale risposta è corretta.

DEFINIZIONE   P è la classe dei problemi di riconoscimento per i quali esiste un algoritmo polinomiale.

OSSERVAZIONE   Tutti i problemi delle liste A e B sono in NP, ma solo per i problemi della lista A possiamo dire che appartengono a P.

OSSERVAZIONE   Se un problema di riconoscimento è in P anche il corrispondente problema di ottimizzazione lo è (utilizzando la tecnica di bisezione sul valore della funzione obbiettivo).

DOMANDA: i problemi della lista B hanno qualcosa in comune oltre il fatto di essere in NP e di non disporre (almeno per ora) di un algoritmo di soluzione polinomiale ?

RISPOSTA:   ebbene SI ! I corrispondenti problemi di riconoscimento sono dimostrabilmente tra i più difficili della classe NP.

DEFINIZIONE   Se P e Q appartengono a NP, e ogni istanza di P può essere convertita in una istanza di Q in tempo polinomiale, in modo che risolvendo quest' ultima si può risalire ad una soluzione di P, si dice che P si riduce polinomialmente a Q (e si scrive P _PQ).

DEFINIZIONE   Indichiamo con NPC la classe dei problemi NP-completi, cioè la classe dei problemi P in NP tali che qualunque problema Q in NP si può ridurre polinomialmente a P.

Ma chi ci dice che NPC non sia vuota ?

TEOREMA (Cook 1971) Il seguente problema è NP-completo:

dato N= e 2m sottinsiemi C_i e D_i , i=1,.,m di N, esiste una soluzione ammissibile al seguente problema binario (cioè con xIⁿ)

S S 1 per i=1,.,m ?

NOTA Il problema così formulato non è altro che il problema di SODDISFACIBILITA' di una espressione Booleana in forma congiuntiva normale come problema di PL binaria.

LEMMA DI RIDUZIONE    Supponiamo che due problemi P e Q siano in NP. Allora

(i)         se QIP e P è riducibile polinomialmente a Q, allora PIP

(ii)       se P è NP-completo e P è polinomialmente riducibile a Q, allora anche Q è NP-completo.

COROLLARIO   Se P NPC F (=insieme vuoto) allora P=NP.

DEFINIZIONE   Un problema di ottimizzazione il cui corrispondente problema di riconoscimento è NP-completo si dice NP-difficile.

DOMANDA: come possiamo mostrare che un problema è in P ?

La risposta più ovvia è: trovando un algoritmo polinomiale per la sua soluzione. Un altro modo (indiretto) è di ricorrere ad una riduzione polinomiale ad un altro problema che sappiamo essere in P.

Ma c' è un altro importante modo:

data una famiglia di poliedri associata ad un problema come ad esempio l' inviluppo convesso dei vettori caratteristici dei punti ammissibili,

il problema di ottimizzazione

max

è risolvibile in tempo polinomiale se e solo lo è il seguente problema di separazione

"dire se xIconv(S) e, in caso contrario,

trovare una disuguaglianza soddisfatta

da tutti i punti di S ma non da x,

cioè un iperpiano che separi x da S".