Lezioni Lincee di Scienze Informatiche

Come vincere un milione di dollari e vivere felici:

il problema P verso NP

Giorgio Ausiello Dip. di Ingegneria Informatica Automatica e Gestionale

'Sapienza' Università di Roma

Roma, 6 Maggio 2014

La precedente scena è tratta dal serial 'Elementary' Un'altro riferimento al tema di questa lezione è nel serial Numb3rs, episodio ‘Uncertainty principle’ Charlie, il fratello matematico dell'agente dell'FBI Don Eppes, disgustato dalla violenza della criminalità si ritira a studiare e cerca di risolvere un celebre problema informatico: il problema ‘P verso NP’ (nel doppiaggio chiamato erroneamente ‘P contro NP’).

In questa presentazione cercheremo di spiegare: • che cosa è questo problema, • perché è così famoso, • perché un importante istituto di matematica offre un milione

di dollari in premio a chi lo risolve.

Tre problemi Abbiamo già visto che il problema del percorso Hamiltoniano (a differenza di quello del percorso Euleriano) è un problema per il quale non si conoscono algoritmi che 'sostanzialmente' non esaminino tutti i possibili percorsi (metodo di forza bruta). Ora vediamo altri tre classici problemi: - il problema della divisione dell'eredità - il problema del commesso viaggiatore - il problema delle disequazioni con variabili binarie.

Il problema della divisione dell’eredità. Due sorelle devono dividere i gioielli ereditati dalla madre in modo che ciascuna ottenga lo stesso valore. Ad esempio gli oggetti hanno valore: 8, 15, 17, 21, 24, 25, 30, 32. Una soluzione può essere di attribuire gli oggetti di valore 8, 15, 17, 21, 25 (= 86) ad una e i rimanenti all’altra. Con 20 oggetti la soluzione va cercata tra (220 - 2)/2, circa 500.000 possibilità. Con 100 oggetti abbiamo un costo dell’ordine di 299. Se ogni possibilità venisse analizzata in un nanosecondo avremmo comunque un tempo di circa 100 miliardi di anni (superiore alla vita dell’Universo).

Il problema del commesso viaggiatore (TSP). Data la mappa delle strade che collegano n città e i relativi costi di percorrenza un commesso viaggiatore che deve visitare tutte le n città e tornare al punto di partenza deve decidere se il budget che ha a disposizione glielo consente. Il problema si definisce in genere su un grafo completo (ogni città è collegata a tutte le altre). Se il grafo non è completo, come abbiamo visto, è già difficile stabilire se esiste un percorso di visita che passa una sola volta in ogni città (problema del percorso Hamiltoniano).

Se ad esempio il budget è 15 e i costi sono quelli indicati Roma Ancona 8 4 3 5 3 Napoli 7 Bari Gli itinerari possibili hanno costo 23, 22 e 15. L'unica soluzione ammissibile è l’itinerario Roma-Bari-Ancona-Napoli-Roma.

Nel caso peggiore i possibili itinerari da analizzare sono (n-1)!/2. Fissata la città di partenza le seconde possono essere 19, le terze 18 e così via, tenendo conto che ogni percorso può essere realizzato in due direzioni. Per n=20 si dovrebbero analizzare 121.645.100.408.832.000/2 percorsi impiegando un tempo pari a circa 2 anni (se, anche in questo caso ogni percorso potesse essere analizzato in un nanosecondo). Tecniche algoritmiche più sofisticate permettono di risolvere il TSP con un costo computazionale dell’ordine di n22n – ma sempre esponenziale!

Le disequazioni con variabili binarie (PL-(0,1)). Dato un sistema di disequazioni lineari esiste una assegnazione di valori 0 o 1 alle variabili che soddisfa tutte le equazioni? Ad esempio, le disequazioni 3x + 5y – z ≥ 2 2x – 3y + 2z ≥ 4 sono entrambe soddisfatte se assumiamo x=1, y=0, z=1 mentre non lo sono se assumiamo x=1, y=1, z=0. Se abbiamo m disequazioni ed n variabili le soluzioni possibili sono 2n e il tempo necessario per trovare (se esiste) una assegnazione di valori che soddisfa tutte le disequazioni è dell’ordine di m2n.

Cosa hanno in comune questi problemi? Tutti questi problemi, e altre migliaia di problemi di grande interesse pratico, allo stato attuale delle conoscenze, sono difficili da risolvere. Per essi si conoscono solo algoritmi sostanzialmente di tipo 'forza bruta', di costo esponenziale MA nessuno ha mai dimostrato che non possono esistere algoritmi più efficienti, di costo polinomiale, cioè nessuno ha mai dimostrato che tali problemi sono veramente difficili.

Come si è visto, se è necessario utilizzare un metodo di forza bruta il costo di risoluzione è esponenziale e quando la dimensione di un problema da risolvere cresce (100 gioielli da dividere, 100 città da visitare!) neanche potenti computer lo possono risolvere.

In pratica è necessario: - adottare tecniche specifiche per i particolari casi che si devono risolvere; così ad esempio è stato risolto il problema del commesso viaggiatore in vari casi reali fino ad un massimo (record attuale) di 85.900 città oppure: - risolvere il problema in modo approssimato; ad esempio se un grafo rispetta la disuguaglianza triangolare si può trovare abbastanza facilmente un percorso lungo al massimo il 50% più dell'ottimo.

Una regola intuitiva (ma con solide basi matematiche). Se un problema richiede tempo polinomiale è facile; se richiede tempo esponenziale è difficile. P: classe di problemi risolubili in tempo polinomiale con macchine di Turing. Se un problema appartiene alla classe P è ritenuto 'facile da risolvere'. Anche se richiede tempo n100? SI (almeno in prima approssimazione - vedi quanto esposto nella lezione precedente).

La classe P viene assunta come sinonimo di classe di 'problemi facili', 'problemi computazionalmente trattabili'. Intuizione di Jack Edmonds (anni '60 - primo algoritmo polinomiale per il matching): “I am claiming, as a mathematical result, the existence of a good algorithm for finding a ... matching in a graph. There is an obvious finite algorithm, but that algorithm increases in difficulty exponentially with the size of the graph. It is by no means obvious whether or not there exists an algorithm whose difficulty increases only algebraically with the size of the graph.”

Tesi di Cobham (1964 - in analogia alla Tesi di Church-Turing che afferma che ogni problema risolubile mediante algoritmi di qualunque natura è risolubile mediante macchine di Turing): P è la classe dei problemi 'trattabili' - Ogni 'ragionevole' modello di calcolo porta a definire la stessa classe di problemi risolubili in tempo polinomiale. Macchine quantistiche?

Come sappiamo se un problema è facile o difficile? La questione fondamentale per sapere se un problema sia facile o difficile da risolvere, è dunque stabilire se appartenga o no alla classe P. Come si individua la reale complessità di risoluzione di un problema?

Per caratterizzare la complessità di un problema servono due informazioni:

- quanto tempo basta per risolverlo (upper bound – limite superiore)

- quanto tempo è indispensabile per risolverlo (lower bound – limite inferiore)

Ad esempio per ordinare un insieme di n numeri interi:

- n log n confronti bastano (algoritmo merge-sort) - n log n sono indispensabili (per individuare uno fra n!

ordinamenti nel caso più sfavorevole servono almeno log (n!) ≈ n log n confronti)

In questo caso la complessità del problema è caratterizzata esattamente (upper bound e lower bound coincidono): la complessità dell’ordinamento è n log n.

Nel caso dei 3 problemi citati prima invece:

- upper bound: 2n - lower bound: n2

Grande divario – grande incertezza sulla effettiva complessità. Scoprire se i 3 problemi sono veramente difficili o se esistono algoritmi che li possono risolvere in tempo polinomiale è di grande rilevanza.

Questo vale non solo per i nostri 3 problemi ma anche per altre migliaia di problemi di grande importanza: - investimenti - trasporti - localizzazione di impianti - progetto di reti di distribuzione Provate a cercare su Facebook il maggior gruppo di vostri amici che sono tutti amici tra loro (problema della massima cricca).

NOTA BENE: La complessità di un problema non è solo una caratteristica negativa. Sulla complessità di alcuni problemi (come ad esempio il problema della fattorizzazione) sono basate tecniche di crittografia usate per garantire la sicurezza delle transazioni elettroniche!

Visto che non ne conosciamo la complessità con esattezza come possiamo caratterizzare i problemi visti precedentemente? Nel tentativo di caratterizzare la complessità dei nostri 3 problemi possiamo utilizzare un altro modello di calcolo: gli algoritmi non deterministici. Un calcolo non-deterministico non si sviluppa come una sequenza di passi ma come un albero. NP: classe di problemi risolubili in tempo polinomiale ma con algoritmi 'non-deterministici'

Ad esempio nel caso del sistema di disequazioni un algoritmo non deterministico 'prova' tutti i valori possibili per le variabili. x=0 x=1 y=0 1 0 y=1 z=0 1 0 1 0 1 0 z=1 N N N N N SI N N Ricordate Nicholas Cage in Next?

I nostri 3 problemi sono tutti risolubili in tempo polinomiale se utilizziamo un modello di calcolo non deterministico. Essi appartengono alla classe NP. In realtà possiamo dire di più: essi sono nella classe dei più 'difficili' problemi appartenenti ad NP: sono NP-completi. Problemi NP-completi: problemi appartenenti a NP e tali che ogni problema in NP si può trasformare in tempo polinomiale ad essi.

Soddisfacibilità di formule del calcolo proposizionale (SAT) Data una formula del calcolo proposizionale in forma normale congiuntiva esiste un'assegnazione di valori di verità alle variabili che la rende vera? Ad esempio: (p ∨ ¬q ∨ r) ∧ (p ∨ q ∨ ¬r) ∧ (¬p ∨ ¬q ∨ r) è soddisfacibile perchè la rendiamo vera se assumiamo p = VERO, q = FALSO, r = FALSO oppure p = FALSO, q = VERO, r = VERO (p ∨ ¬q) ∧ (p ∨ q) ∧ (¬p ∨ ¬q) ∧ (¬p ∨ q) invece non è soddisfacibile.

Il problema della soddisfacibilità è il primo problema che è stato dimostrato NP-completo (S. Cook, 1971) Ogni problema risolubile in tempo polinomiale con macchine non deterministiche (cioè ogni problema in NP) può essere 'ricondotto' in tempo polinomiale al problema SAT. A partire da SAT altri problemi sono stati dimostrati NP-completi.

Ad esempio possiamo mostrare che data una formula w di SAT possiamo costruire in tempo polinomiale un sistema di disequazioni Sw che ammette soluzione se e solo se w è soddisfacibile. Sia w la formula (p ∨ ¬q ∨ r) ∧ (p ∨ q ∨ ¬r) ∧ (¬p ∨ ¬q ∨ r) con variabili logiche p, q, r, il sistema Sw di disequazioni con variabili in 0, 1 xp, xq, xr è il seguente: xp + (1- xq) + xr ≥ 1 xp + xq + (1 - xr) ≥ 1 (1 - xp) + (1- xq) + xr ≥ 1

NP

P

NP-completi

PSPACE

EXPTIME

Ad oggi i problemi NP-completi noti sono diverse migliaia. Tutti questi problemi hanno le stesse caratteristiche: - per essi conosciamo solo algoritmi di costo esponenziale - se per uno solo di essi si dimostrasse che algoritmi polinomiali non esistono si avrebbe la prova che le due classi P ed NP sono diverse - se per uno solo di essi si trovasse un algoritmo polinomiale vorrebbe dire che per tutti gli altri problemi NP-completi esisterebbe un algoritmo polinomiale (sarebbero tutti facili da risolvere) e si avrebbe che le due classi P ed NP coincidono.

Il problema da un milione di dollari La classe P e la classe NP sono distinte o coincidono? (problema definito nel 1971 da S. Cook e aperto da allora) In altre parole, esiste un problema in NP (in particolare uno dei nostri 3 problemi o uno qualunque delle migliaia di problemi NP-completi noti) per il quale si può mostrare che non esiste alcun algoritmo polinomiale?

OPPURE, AL CONTRARIO E' possibile trovare un algoritmo di costo polinomiale per qualcuno dei problemi NP-completi?

Se si scoprisse che P = NP: allora migliaia di problemi di grande interesse pratico potrebbero essere risolti in tempo polinomiale - sarebbero facili! Se si scoprisse che P ≠ NP: allora si saprebbe che per quei problemi non esistono algoritmi polinomiali - quei problemi sarebbero veramente difficili e potrebbero essere risolti solo in casi particolari o con metodi approssimati! Ma nella questione P verso NP si cela un problema epistemologico più profondo.

Un altro modo di guardare ai problemi NP-completi 1) TROVARE LA SOLUZIONE DI QUESTI PROBLEMI E’ DIFFICILE. Tutti gli algoritmi noti per risolvere questi problemi richiedono tempo esponenziale anche se nessuno ha mai dimostrato che un tempo esponenziale è effettivamente necessario.

MA

2) VERIFICARE LA SOLUZIONE DI QUESTI PROBLEMI E’ FACILE. Per ognuno di questi problemi si può verificare facilmente in tempo polinomiale se una soluzione proposta risolve realmente il problema.

Ad esempio si può agevolmente verificare se una data suddivisione dei gioielli fornisce lo stesso valore alle due sorelle o se un dato itinerario può essere percorso dal commesso viaggiatore rispettando il budget. Tutti noi ci aspettiamo che trovare una soluzione sia 'più difficile' che verificare una soluzione che ci viene proposta. Se al contrario si scoprisse che trovare una soluzione e verificare una soluzione hanno la stessa difficoltà le conseguenze sarebbe sorprendenti.

Il problema del XX secolo. Parigi, 9 agosto 1900 Secondo Congresso Internazionale delle Matematiche David Hilbert formula 23 problemi aperti Sur les Problèmes Futurs des Mathématiques Secondo problema: " Dèmontrer que les axiomes [de l'Arithmétique] ne sont pas contradictoires; c'est à dire démontrer qu'en se basant sur les axiomes l'on ne pourra jamais arriver à des résultats contradictoires au moyen d'un nombre fini de déductions logiques."

Bologna, 3-10 settembre1928 Congresso dell'Unione Matematica Internazionale Hilbert esplicita ulteriormente il problema: - l'aritmetica è completa? - l'aritmetica è coerente? - l'aritmetica è decidible? 1931 Gödel dimostra che l'aritmetica è incompleta (o non coerente!). 1935-36 Alan Turing (e Alonzo Church) dimostrano che l'aritmetica è indecidibile.

Per far ciò Turing: - definisce il concetto d'algoritmo, - definisce il concetto di macchina universale (calcolatore programmabile), - dimostra l'esistenza di problemi indecidibili, problemi che nessun algoritmo (e nessun computer) può risolvere. IL SECONDO PROBLEMA POSTO DA HILBERT ALL'INIZIO DEL XX SECOLO EBBE UN RUOLO INIMMAGINABILE E FONDAMENTALE NEL PROGRESSO DELL'INFORMATICA, DELLA MATEMATICA E DELLE SCIENZE IN GENERALE

Il problema del XXI secolo. Parigi, 24 Maggio 2000 Il Clay Mathematics Institute annuncia la messa in palio di sette premi da un milione di dollari per la soluzione di altrettanti importanti problemi di matematica ancora irrisolti (uno dei quali, la congettura di Poincaré, risolto nel 2010). Prudentemente i problemi vengono chiamati i problemi del millennio e non i problemi del secolo! Il terzo di essi è il problema 'P versus NP'.

Dal sito del Clay Mathematics Institute ".... In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure...." In altre parole, esistono problemi per i quali si richiede tempo esponenziale (impossibly long time) per trovare la soluzione ma è sufficiente tempo polinomiale (quick) per verificare se una soluzione proposta risolve realmente il problema? Cioè la classe P è diversa dalla classe NP?

La soluzione della questione P verso NP richiederà una conoscenza dei concetti del calcolo più approfondita di quelle oggi disponibili e l'uso di tecniche matematiche molto raffinate. CI SI ASPETTA CHE ANCHE IL PROBLEMA P VERSO NP POSTO DAL CLAY MATHEMATICS INSTITUTE ALL'INIZIO DEL XXI SECOLO ABBIA CONSEGUENZE ORA INIMMAGINABILI SULL'INFORMATICA, SULLA MATEMATICA E SULLE SCIENZE IN GENERALE

(vedi Lance Fortnow, The Golden Ticket: ���P, NP, and the Search for the Impossible, 2013)

Finora una lunga serie (40 anni!) di fallimenti: - nel tentativo di dimostrare P=NP illudendosi di aver trovato un algoritmo polinomiale per qualche problema NP-completo - nel tentativo di dimostrare P≠NP illudendosi di aver trovato la dimostrazione che qualche problema NP completo richiede necessariamente un algoritmo di costo esponenziale ... ma non si sa mai!

BUONA FORTUNA !