Cenni di complessità computazionale¶

Parte 1 · Problemi di ottimizzazione combinatoria · Capitolo 1 · Capitolo 1: Ottimizzazione combinatoria · Dispensa, volume 1 (PDF) · Slide · Esercizi: Ottimizzazione combinatoria · App: Forza bruta sul problema dello zaino 0/1

1.6 Cenni di complessità computazionale¶

La forza bruta richiede tempo esponenziale. Esiste un algoritmo che risolve un problema di ottimizzazione combinatoria in tempo polinomiale? La complessità computazionale classifica i problemi in base a questa domanda; qui diamo solo le definizioni che servono nel corso.
La dimensione di un'istanza è il numero di bit necessari per scriverla. Per esempio, un'istanza con \(n\) numeri, il più grande dei quali è \(M\), ha dimensione dell'ordine di \(n \log_2 M\): un numero \(M\) si scrive con circa \(\log_2 M\) bit, non con \(M\) simboli.
Un algoritmo è polinomiale se il suo tempo di esecuzione è limitato da un polinomio nella dimensione dell'istanza.
La versione decisionale di un problema di ottimizzazione pone una domanda sì/no, per esempio: “esiste una soluzione ammissibile di valore almeno \(k\)?”.

Definizione 1.7: le classi P e NP

P è la classe dei problemi decisionali che si possono risolvere con un algoritmo polinomiale.
NP è la classe dei problemi decisionali le cui istanze “sì” ammettono un certificato che si può verificare in tempo polinomiale (per esempio, una soluzione ammissibile di cui ammissibilità e valore si calcolano in tempo polinomiale).
Un problema decisionale in NP è NP-completo se ogni problema in NP si può ridurre a esso in tempo polinomiale. Un problema di ottimizzazione è NP-hard se la sua versione decisionale è NP-completa (più in generale, se un algoritmo polinomiale per esso darebbe un algoritmo polinomiale per un problema NP-completo).

Non è noto se \(P = NP\). Non si conosce alcun algoritmo polinomiale per un problema NP-completo, ed è opinione diffusa che non ne esista nessuno: per un problema NP-hard non ci aspettiamo un algoritmo esatto polinomiale.

1.6.1 Algoritmi pseudo-polinomiali e problemi NP-hard in senso forte¶

Alcuni problemi NP-hard si possono risolvere in tempo polinomiale in \(n\) e nel valore dei numeri dell'istanza. Per esempio, un algoritmo che richiede tempo \(O(n\,M)\), dove \(M\) è il numero più grande dell'istanza, non è polinomiale: \(M\) è esponenziale nel suo numero di bit \(\log_2 M\).

Definizione 1.8: algoritmo pseudo-polinomiale, problemi NP-hard in senso debole e forte

Un algoritmo è pseudo-polinomiale se il suo tempo di esecuzione è limitato da un polinomio nella dimensione dell'istanza e nel numero più grande che vi compare.
Un problema NP-hard è NP-hard in senso forte se resta NP-hard quando tutti i suoi numeri sono limitati da un polinomio nella dimensione dell'istanza (equivalentemente, quando i numeri sono scritti in unario). Altrimenti, se ammette un algoritmo pseudo-polinomiale, si dice NP-hard in senso debole (NP-hard in senso ordinario).

Un problema NP-hard in senso forte non ha algoritmi pseudo-polinomiali, a meno che \(P = NP\).

Che un problema sia NP-hard non significa che un'istanza non si possa risolvere: significa che non ci aspettiamo un algoritmo che risolva ogni istanza in tempo polinomiale. In pratica combiniamo metodi esatti che chiudono il gap fra bound primali e duali, euristiche che trovano rapidamente buone soluzioni, e algoritmi di approssimazione che garantiscono un gap limitato nel caso peggiore.

I problemi dei prossimi capitoli sono tutti NP-hard: il problema dello zaino 0/1 è NP-hard in senso debole, mentre il bin packing, la colorazione dei vertici, la clique massima e il problema del commesso viaggiatore sono NP-hard in senso forte. Ogni capitolo discute la complessità del suo problema.

1.7 Errori tipici¶

Attenzione

Confondere soluzioni candidate e ammissibili. I numeri \(2^n\), \((n-1)!/2\) e \(B(n)\) contano le candidate; le soluzioni ammissibili possono essere molte meno, per esempio \(11\) sottoinsiemi su \(16\) nell'Esempio 1.1.
Scambiare i due versi dei bound. In un problema di massimo un bound primale è un lower bound e un bound duale è un upper bound; in un problema di minimo i ruoli si scambiano.
Arrotondare un bound duale quando l'obiettivo non è intero. L'arrotondamento dell'Osservazione 1.6 richiede \(f(S) \in \Z\) per ogni soluzione ammissibile.
Contare due volte soluzioni equivalenti. Un ordinamento ciclico e il suo inverso sono lo stesso ordinamento ciclico, e due assegnamenti che differiscono per una ridenominazione di etichette intercambiabili sono la stessa soluzione.
Leggere NP-hard come irrisolvibile. Essere NP-hard è un'affermazione sul caso peggiore: molte istanze di dimensione pratica si risolvono, e il resto del corso mostra come.

1.8 In sintesi¶

In sintesi

Un problema di ottimizzazione combinatoria ha un insieme base finito, una famiglia di sottoinsiemi ammissibili e una funzione obiettivo; una soluzione ottima esiste quando esiste una soluzione ammissibile.
La categoria delle decisioni dà l'oggetto combinatorio di una soluzione: un sottoinsieme, un vettore di quantità intere, un assegnamento, un ordinamento o una partizione.
Le soluzioni candidate sono \(2^n\) sottoinsiemi, \(n!\) ordinamenti, \((n-1)!/2\) ordinamenti ciclici e \(B(n)\) partizioni: la forza bruta funziona solo su istanze molto piccole.
Una soluzione ammissibile dà un bound primale, un rilassamento o un argomento combinatorio dà un bound duale; un gap nullo certifica che la soluzione ammissibile è ottima.
I problemi del corso sono NP-hard: per essi non ci aspettiamo un algoritmo esatto polinomiale.

Quadro riassuntivo della piccola istanza.

Esempio 1.1 (max)	lower bound	upper bound	da
primi bound	\(11\)	\(14\)	scelta greedy, uno dei pesi \(7\) e \(6\)
bound finali	\(13\)	\(13\)	soluzione \(\{2,3,4\}\), argomento sulla cardinalità

Esercizi su questo capitolo: Ottimizzazione combinatoria