Showing posts with label problemi NP-completi. Show all posts
Showing posts with label problemi NP-completi. Show all posts

20 August 2010

Fra P e NP(-completi)

 
Proseguo dal post precedente.
E' venuto fuori un post molto lungo, anche se più breve di quel che avrei voluto...
 
Chiariamo innanzitutto alcuni aspetti del tutto generali sui criteri alla base della classificazione della complessità computazionale di un problema.
 
Efficienza algoritmica come limite superiore alla complessità di un problema
 
La legge di scala (polinomiale, esponenziale, etc) delle risorse computazionali (tempo, memoria, etc) in ragione della taglia del problema (le cifre del numero da fattorizzare, il numero di amminoacidi della proteina da foldare) è, strettamente parlando, una caratteristica dell'algoritmo, non del problema: posso infatti benissimo immaginare di risolvere un problema P con un algoritmo che scala esponenzialmente, basta essere sufficientemente "ingenuo" e "sprecone".
Dato però un algoritmo capace di risolvere un certo problema, posso comunque dire qualcosa sulla complessità computazionale del problema: essa certamente non sarà superiore alla complessità dell'algoritmo. 
Quando dunque voglio parlare di complessità di un problema in termini di risorse, dovrò necessariamente parlare di complessità non maggiore di quella del miglior algoritmo noto: potrà sempre succedere di scoprire un algoritmo più efficiente per un problema, dimostrando così che la sua complessità computazionale era effettivamente più piccola di quella che credevamo (e storicamente è proprio successo così per alcuni problemi che sembravano più "difficili" di quel che erano, uno per tutti il test di primalità, il problema, cioè, di stabilire se un numero è primo o meno — senza dover trovare esplicitamente i suoi fattori primi). 
L'unico modo che avremmo per poter dire che un problema è davvero, intrinsecamente "difficile" sarebbe quello di dimostrare che non è matematicamente possibile trovare un algoritmo più efficiente di una certa complessità, ma questo finora, che io sappia, non è mai accaduto per nessun problema. 
Di conseguenza, dunque, le classi di complessità dei problemi tendono ad essere degli insiemi "concentrici" in cui le classi più "complesse" includono quelle più semplici (e.g. P è un sottoinsieme di NP). In realtà non è sempre necessariamente così per tutte le possibili classificazioni e comunque quasi sempre non abbiamo garanzie che l'inclusione sia propria, che esistano cioè problemi che hanno una qualche complessità minima (e.g. un problema che sia in NP ma non in P — che equivarrebbe appunto a dimostrare che P!=NP). 
 
Esempi semplici 
 
Chiarito il senso generale del concetto di "classe di complessità di un problema", possiamo passare ad alcune classi specifiche: P è la classe di problemi per cui si conosce un algoritmo di soluzione che scala polinomialmente nel tempo, EXP quella dei problemi di cui si conosce un algoritmo di soluzione che scala esponenziale nel tempo; PSPACE è quella dei problemi di cui si conosce un algoritmo di soluzione che scala polinomialmente nell'uso di memoria (space), fosse anche in tempo infinito. Evidentemente, per quanto detto prima, P è un sottoinsieme di EXP. Si può poi dimostrare che PSPACE è un sottoinsieme di EXP e dunque la catena di inclusioni "concentriche" è: EXP ⊇ PSPACE ⊇ P. 
 
NP 
 
Bene, veniamo dunque ai problemi NP. La classe NP è definita in modo un po' diverso (è per questo che dicevo che non tutte le classi sono "concentriche": ad esempio sia NP che coNP includono P, ma entrambe non sono (probabilmente) l'una il sottoinsieme dell'altra — a meno che NP=coNP o addirittura che P=NP, e allora sarebbe P=NP=coNP... Se vi interessa dare uno sguardo "grafico" allo Zoo della complessità potete dare un'occhiata a uno di questi diagrammi delle inclusioni; se vi interessano i dettagli potete perdervi nel Complexity Zoo Qwiki). 
Dicevamo, NP: si può definire la classe NP con una legge di scala degli algoritmi, ma per farlo bisogna cambiare definizione di algoritmo: i problemi NP sono quelli per cui è noto un algoritmo non-deterministico (da cui la N della sigla NP) capace di risolverlo in tempi polinomiali. Gli algoritmi non-deterministici (o equivalentemente le macchine di Turing non-deterministiche) rappresentano un modello computazionale molto utile a livello teorico ma di scarsa rilevanza pratica, dal momento che non è possibile costruirne una realizzazione fisica. Praticamente tutti i moderni computer sono invece delle macchine di Von Neumann che implementano una macchina di Turing universale deterministica, e infatti quando si parla di algoritmi senza ulteriori specificazioni si intendono sempre algoritmi deterministici o per macchine di Turing deterministiche
Esiste però una definizione del tutto equivalente, che tira in ballo i soliti algoritmi deterministici: i problemi NP sono quei problemi per cui è noto un algoritmo (deterministico) capace di verificare la soluzione in tempi polinomiali. 
Per la cronaca, i problemi NP stanno fra PSPACE e P, ovvero: EXP ⊇ PSPACE ⊇ NP ⊇ P. 
 
NP-completezza: un limite inferiore alla complessità di un problema? 
 
E i tanto chiacchierati problemi NP-completi? Qui le cose si fanno più intricate... e più affascinanti. In effetti quella dei problemi NP-completi non è nemmeno una classe di complessità in senso proprio del termine (non la troverete, infatti, nel super-mega-complicatissimo-diagramma-di-inclusione). 
Il punto cruciale è che la definizione di problema NP-completo cerca di fare quello che le classi di complessità di cui abbiamo parlato finora non possono fare: rappresentare un limite inferiore alla complessità di un problema. Dico cerca perché, ovviamente, se ci riuscisse veramente avrebbe appunto dimostrato che P≠NP. E tuttavia, pur non riuscendoci, il procedimento escogitato per la definizione di NP-completezza, la riduzione polinomiale, è in grado di gettare nuova luce su tutta teoria della complessità computazionale. 
Abbiamo, dunque, molti problemi NP che ci sembrano difficili. Ma alcuni di essi, come il test di primalità, abbiamo scoperto essere solo apparentemente difficili — nel 1975 si riuscì a dimostrare che il test di primalità era un problema NP, ma ci vollero 27 anni perché fosse "risolto" con un algoritmo polinomiale
Come distinguere, dunque, i problemi che sembrano difficili da quelli che lo sono davvero? Distinguerli proprio sulla base della difficoltà è una petizione di principio, significherebbe sapere che sono difficili, ovvero che P≠NP. Quello che fa, invece, la definizione di NP-completezza è trovare una caratteristica comune a quasi tutti i problemi che, ancora oggi, ci paiono difficili, caratteristica che invece non hanno i problemi facili, che stanno in P. Di più: questa caratteristica è tale per cui, se davvero P≠NP, allora i problemi in NP che non stanno in P sono proprio (almeno) i problemi NP-completi. Detto più precisamente, i problemi NP-completi sono certamente "i più difficili" fra i problemi NP (sempre se P≠NP, altrimenti "tutti i problemi NP sono facili come quelli in P"). 
Quel quasi tutti si riferisce al fatto che esistono alcuni problemi NP che ci paiono difficili (cioè di cui non abbiamo ancora trovato un algoritmo polinomiale per risolverli) ma che non siamo riusciti a dimostrare essere NP-completi — e il problema della fattorizzazione dei numeri composti, alla base di quasi tutte le tecniche crittografiche usate comunemente, è proprio uno di questi. Se davvero P≠NP e dunque non tutti i problemi NP sono ugualmente facili, ciascuno di questi problemi potrebbe, più o meno indipendentemente dagli altri:
  • essere "semplicemente" un problema P, come il test di primalità, e un giorno, chissà, riusciremo a trovare un algoritmo di soluzione polinomiale;
  • essere anch'esso un problema NP-completo, solo che ancora non siamo riusciti a dimostrarlo;
  • essere di una complessità computazionale intermedia.
E qui arriva il bello. 
 
Riduzione polinomiale, NP-hard e, finalmente, la definizione di NP-completezza 
 
Ho quasi finito, ma, prima di concludere con la questione della fattorizzazione e delle tecniche crittografiche, direi che è il caso di spiegare in cosa consiste questa mitica NP-completezza, la proprietà di alcuni problemi NP che sembra caratterizzarne la (apparente) difficoltà. 
L'elemento fondamentale è il concetto di riduzione e in particolare di riduzione polinomiale. Ne esistono di due tipi diversi (di Cook e di Karp), ma per amor di brevità sarò impreciso e dirò che ho ridotto il problema A al problema B se, data la soluzione del problema A, so trovare la soluzione al problema B con un algoritmo al più polinomiale. Definisco ora un problema B come NP-hard se un qualsiasi problema NP può essere ridotto polinomialmente a B: se, cioè, con un oracolo capace di darmi istantaneamente la soluzione di B, so risolvere qualsiasi problema NP in tempi polinomiali. Definisco finalmente i problemi NP-completi come quei problemi NP-hard che siano anche problemi NP. 
Come al solito le definizioni sono mere convenzioni e dunque il fatto notevole è che nei primi anni 70 Cook, Karp e Levin mostrarono non tanto che esistono problemi NP-completi quanto che molti problemi concreti erano proprio NP-completi
Il fatto che una soluzione "facile" ad uno qualsiasi di questi problemi dischiuderebbe automaticamente le porte a tutti gli altri problemi in NP ne fa chiaramente i rappresentati "più difficili" della classe NP. Non solo: ci dice anche che la "difficoltà" dei problemi NP-completi è essenzialmente la stessa, come se si trattasse di un unico problema sotto diverse sembianze: se uno qualunque di questi problemi ha una soluzione facile, allora tutti quanti ce l'hanno e, di fatto, P=NP; se riuscite a dimostrare che uno qualunque di essi non può avere una soluzione polinomiale, allora nessun'altro potrà averla e, di fatto, avete dimostrato che P≠NP; uno per tutti, tutti per uno.
Per dimostrare, dunque, che un problema NP è NP-completo è sufficiente dimostrare che è riducibile ad uno qualsiasi degli altri problemi di cui è stata già dimostrata la NP-completezza. La scoperta di problemi NP-completi procedette perciò con un effetto valanga: più problemi rientravano nella categoria, più facile diventata ricondurvene di nuovi. Le dimostrazioni di NP-completezza diventarono routine e al momento si contano più di tremila problemi NP-completi.
 
Il problema della fattorizzazione: fra P e NP-completi 
 
Esistono però alcune — poche — notevoli eccezioni: problemi NP, cioè, che (ancora) ci paiono difficili (e dunque sospettiamo non siano P), di cui purtuttavia non si riesce a dimostrare l'NP-completezza. Esempi di problemi di questo tipo sono l'isomorfismo fra grafi, il logaritmo discreto e, udite udite, il problema della fattorizzazione
Del resto ci sono ragioni piuttosto profonde per credere che la fattorizzazione non sia un problema NP-completo: per esempio un'istanza di problemi NP-completo può, in generale, avere nessuna, una o centomila soluzioni diverse; la fattorizzazione di un numero composto, invece, è unica. Questa sorta di struttura del problema della fattorizzazione è in effetti sfruttata dal crivello dei campi di numeri, il miglior algoritmo noto di fattorizzazione, che scala più o meno come 2 alla radice cubica di n, qualcosa che qualcuno definisce pur sempre come un andamento sub-esponenziale.
Le possibili relazioni fra P, NP e coNP. Se il problema della fattorizzazione fosse NP-completo, la relazione corretta sarebbe la (b).
Inoltre il problema della fattorizzazione non solo appartiene a NP ma anche coNP, la classe di complessità complementare a NP secondo una precisa definizione che non mi dilungherò a discutere (è già diventato troppo lungo questo post, devo sbrigarmi a chiudere!). Ora, la relazione (insiemistica) fra NP e coNP (ed anche con P) non è nota con certezza matematica, ma ci sono diversi indizi che suggeriscono che NP≠coNP. Ebbene, se la fattorizzazione fosse NP-completa, significherebbe proprio che NP=coNP. Per quel che ne sappiamo, poi, potrebbe pure darsi che l'intersezione fra NP e coNP (a cui certamente appartiene il problema della fattorizzazione) coincida con P stesso (ovvero la fattorizzazione è risolvibile in tempo polinomiale) e purtuttavia P e NP non coincidano! 
Per non parlare, poi, del fatto che per il problema della fattorizzazione, e non per alcun problema NP-completo, siamo riusciti a trovare un algoritmo quantistico, quello di Shor, capace di trovare la soluzione in tempi polinomiali. 
Ma, appunto, non ne parlerò, si è già fatto troppo tardi. 
Sono sicuro che non è rimasto più nessuno, fin qui, a leggere... :-)

17 August 2010

La fattorizzazione non è un problema NP-completo (che si sappia)

Questa storia della dimostrazione (ormai quasi definitivamente smontata) che P≠NP sta riportando in superficie il diffusissimo errore secondo cui se P≠NP allora i crittografi e i loro clienti potranno dormire sonni tranquilli (ho citato la mia amica Sylvie, ma è un'affermazione piuttosto frequente).
L'errore consiste nel considerare il problema della fattorizzazione dei numeri composti un problema NP-completo, cosa che non è affatto dimostrata e, anzi, ci sono forti indicazioni che portano a credere che non sia tale: se avete tempo, vi ri-consiglio caldamente tutte le lezioni del corso di Scott Aaronson: Quantum Computing Since Democritus; se avete fretta e vi interessa la questione della "difficoltà" della fattorizzazione, potete limitarvi alla lezione n° 6: P, NP, and Friends.
Che quello della fattorizzazione sia un problema NP-completo è un fraintendimento molto diffuso, io lo scoprii proprio quando mi imbattei nelle lectures di Scott Aaronson: in realtà molto probabilmente si tratta di un problema "più semplice" dei problemi NP-completi, per cui potrebbe benissimo darsi che si scopra che sia un problema "facile" (P) senza che ciò implichi che siano facili anche i problemi NP-completi (molto più probabilmente si tratta di un problema che ricade in un classe intermedia fra P e NP). Detto al contrario: anche se fossimo in grado di dimostrare che i problemi NP-completi sono "davvero" difficili, il problema della fattorizzazione dei numeri composti (e dunque il problema di violare un codice crittografico) potrebbe benissimo rientrare nella categoria dei problemi "facili" (P).
Tant'è che per il problema della fattorizzazione esiste un algoritmo quantistico (il famoso algoritmo di Shor) capace di risolverlo in tempo polinomiale, mentre — nonostante si senta spesso dire il contrario — non è noto alcun algoritmo quantistico capace di risolvere problemi NP-completi in tempo polinomiale, e se mai un giorno si dovesse scoprirne uno, sarebbe sicuramente molto diverso dall'algoritmo di Shor.
Vi siete persi?
Spero di riuscire a buttar giù un "riassuntino" della faccenda quanto prima (cioè: ho già cominciato a scrivere qualcosa, ma sta venendo più lungo di quel che credessi; così ho pensato di uscire subito con questo post giusto per (tentare di) restare "sulla notizia"...).
 
Prima di chiudere, però, vorrei dire due parole sul perché questa questione dell'equivalenza (o meno) delle classi P e NP mi appassiona tanto.
Il fatto è che non si tratta di uno dei problemi da un milione di dollari, o di uno dei più difficili problemi matematici ancora irrisolti, ma si tratta del Problema tout court: se tutti i problemi NP fossero risolvibili polinomialmente, sarebbe possibile programmare un computer per risolvere in poco tempo anche tutti gli altri problemi da un milione di dollari.
C'è addirittura chi crede che l'impossibilità algoritmica di risolvere problemi NP-completi in tempo polinomiale sia consustanziale alla stessa struttura fisica di cui è fatto il mondo.
Come chi?, ma Scott Aaronson, no? :-)

03 June 2008

genetic algorithms

Biology employs what computer scientists know as genetic algorithms. Sometimes biology simply mutates the candidate solutions, but other times it combines them (which we call sexual reproduction).
Biology has adopted the sexual reproduction technique so widely that it must have something going for it, even if we don’t yet fully understand what it is. In experiments, local search algorithms that employ only mutations (i.e. “asexual reproduction”) consistently do better at solving NP-complete problems than do algorithms that incorporate sex.
The best theory people currently have as to why nature relies so heavily on sex is that nature isn’t trying to solve a fixed problem; the constraints are always changing. For example, the features that were ideal for an organism living in the dinosaur age are different from the features that are ideal for modern-day organisms. This is still very much an open issue.

05 June 2007

NP-complete Problems and Physical Reality - 2

Ora, una delle congetture piu' ambiziose e difficili da dimostrare e' proprio quella secondo cui non esistono algoritmi capaci di risolvere i problemi NP-completi in un tempo polinomiale. E l'articolo di Aaronson [›››] affronta esattamente tale questione, ma spostando l'attenzione da un punto di vista strettamente algoritmico ad uno piu' squisitamente fisico. La domanda e': non e' che l'impossibilita' di risolvere efficientemente i problemi NP-completi costitusce una vera e propria limitazione fisica nel nostro universo, esattamente come il limite della velocita' della luce o, forse meglio, come la seconda legge della termodinamica?
Vengono dunque passati in rassegna diversi tipi di dispositivi fisici che possono essere pensati e/o sono stati proposti, almeno in linea di principio, come calcolatori "naturali" capaci di rislovere, eventualmente specifici, problemi. A partire dal caso forse piu' famoso, quello delle bolle di sapone.
   —   ∴   —   
Avete i vostri n punti disposti su un piano e cercate l'insieme di segmenti, di lunghezza complessiva la piu' piccola possibile, che uniscano tutti i punti che avete scelto (i segmenti possono anche incontrarsi in altri ulteriori vertici rispetto ai punti scelti). Si puo' mostrare che questo tipo di problema e' proprio di tipo NP-completo. E puntualmente tutti gli algoritmi di soluzione finora proposti sono in grado di trovare la soluzione in un tempo che cresce esponenzialmente col numero di punti da collegare. Ora, e' un classico esempio di folklore scientifico quello di mostrare come sia possibile trovare la soluzione a un problema di questo tipo utilizzando delle bolle di sapone. Prendete due lastre di vetro tenute parallele da una serie di pioli fissati su entrambe le lastre proprio nelle posizioni dei punti del piano che avevate scelto. Immergendo le due lastre in un bagno di acqua e sapone, e poi risollevandole, e' possibile leggere la soluzione a questo problema nelle lamine di acqua e sapone che si formano tra i pioli (e la spiegazione e' che le bolle di sapone, per questioni energetiche, tendono a minimizzare la propria superficie...). Ora il punto in gioco non e' neanche quello che le bolle di sapone possono fare piu' di un calcolatore tradizionale (macchina di Turing). Si puo' infatti dimostrare che la fisica classica (delle lamine di acqua e sapone) puo' essere simulata per mezzo di "semplici" algoritmi polinomiali. Un esperimento di fisica, dunque, vorrebbe essere nientepopodimenoche' la dimostrazione che esiste un algoritmo tradizionale capace di risolvere un problema NP-completo in tempo polinomiale (pur non fornendo alcun esempio di tale algoritmo).
In realta' non c'e' nessuno scoop, perche', di fatto, non e' vero che l'esperimento delle bolle di sapone e' un buon metodo per risolvere il problema posto. O almeno non sempre. Quello che succede, infatti, e' che le lamine che si formano immergendo le lastre nell'acqua e sapone semplicemente tendono a rilassarsi verso una configurazione piu' stabile che minimizzi la loro superficie (e quindi la lunghezza complessiva dei segmenti corrispondenti). Ma non e' affatto detto che questo processo di assestamento si concluda nella configurazione ottimale in assoluto. Con pochi punti, questo e' quello che (spesso) succede davvero, ma aumentando pian piano il numero di pioli fra le lastre si osserva proprio che la formazione di lamine e' quasi del tutto casuale e, pur con occasionali "semplificazioni" verso configurazioni energeticamente piu' convenienti, risulta tutt'altro che la piu' conveniente.
Del resto c'e' tutta una classe di algoritmi tradizionali che tentano di risolvere istanze di problemi NP-completi proprio attraverso meccanismi di rilassamento verso "stati di minima energia" (come i vetri di spin). La difficolta' di questi algoritmi e' proprio quella della presenza di minimi locali che "intrappolano" l'esplorazione dello spazio delle soluzioni e fanno crescere esponenzialmente i tempi di rilassamento verso la soluzione ottimale cercata.
   —   ∴   —   
Interruzione, penserete voi, significa che sta passando ad un'altro dispositivo o fenomeno fisico. Invece no, c'e' un'ultima cosa da dire su questo punto. E lo stacco grafico ha il solo scopo di consentirmi di dare il necessario rilievo a quello che, secondo me, rappresenta uno dei passaggi piu' profondi dell'articolo di cui sto parlando. Un passaggio che consta di un paio di frasette buttate li' quasi semplicemente a concludere l'argomento, e che hanno invece provocato in me quella straordinaria sensazione che si prova quando si capisce qualcosa di semplice e profondo allo stesso tempo. Seguitemi.
Un esempio del tutto analogo a quello dei vetri di spin e delle bolle di sapone e' quello del ripiegamento delle proteine. Per quello che dicevamo sulla definizione della classe di problemi NP-completi, si potrebbe addirittura pensare di utilizzare delle proteine artificiali come calcolatori, mappando opportunamente la disposizione degli amminoacidi con i vincoli del nostro problema in maniera tale che la configurazione ripiegata della proteina fornisca una codifica per la soluzione al nostro problema di partenza. Ebbene, esattamente come nel caso delle bolle di sapone, nessuno puo' garantirci che il processo di ripiegamento della proteina artificiale non si "incagli" in minimi locali ben lontani dalla vera configurazione di minimo energetico.
Vi e' sorta spontanea la domanda centrale? Come diavolo fanno allora le proteine naturali a ripiegarsi correttamente in tempi rapidissimi? Vi siete gia' risposti? Evidentemente le proteine naturali si sono evolute specificatamente proprio per evitare di incontrare nel processo di ripiegamento, o di avere del tutto, minimi locali in cui incastrarsi (ed eccezioni a questa regola di buon adattamento sono date, per esempio, dai prioni...). [›››]

30 May 2007

NP-complete Problems and Physical Reality − 1

Personalmente ho letto tutto l'articolo [›››] senza ricordarmi cosa fossero esattamente i problemi NP-completi. Se volete essere precisi potete andare sulla wikipedia oppure, molto meglio, potete divertirvi leggendo le lezioni di Aaronson (la quinta e la sesta in particolare, ma a quel punto il consiglio e' di partire dall'inizio...) dove l'ho ri-scoperto io stesso, dopo. Se siete pigri come me, puo' bastare sapere che con l'espressione NP-completi si fa riferimento ad una classe di problemi difficili, dove il concetto di difficolta' puo' essere espresso in maniera tecnicamente piu' precisa (ho scoperto che c'e' un variegatissimo zoo di classi di complessita'...).
In generale i problemi considerati sono caratterizzati da una grandezza variabile n (le cifre del numero da fattorizzare, la lunghezza della proteina da ripiegare...) e gli algoritmi che vengono proposti per risolvere tali problemi sono caratterizzati dalla maniera con cui scalano, all'aumentare di n, le risorse computazionali (memoria, tempo...) richieste dall'algoritmo per risolvere il problema. Ad esempio, un modo di vedere la difficolta' dei problemi NP-completi passa per la constatazione che qualsiasi algoritmo finora proposto per la loro soluzione richiede un tempo che cresce esponenzialmente con n. La definizione della classe di problemi NP-completi non fa esplicito riferimento allo scalare delle risorse richieste per la soluzione. Del resto quella e' una caratteristica di un algoritmo piu' che di un problema. Questo punto di come definire la "classe di difficolta'" di un problema senza far esplicito riferimento al "miglior algoritmo capace di risolverlo" e' molto interessante, lasciatemi spendere qualche parola in piu' (ma ovviamente sto semplicemente seguendo la lezione 6 di Aaronson...!).
   —   ∴   —   
Considerate il problema di saper dire, di un numero a n cifre, se e' primo o composto (senza necessariamente fattorizzarlo). Oppure considerate il problema di soddisfare il meglio possibile le richieste di alloggio in stanze doppie di un numero n di persone, ciascuna con l'indicazione di quale delle altre persone e' il suo "compagno di stanza preferito". Oppure ancora considerate il problema di sapere, date due sequenze di DNA lunghe n basi, quante inserzioni e rimozioni di basi sono necessarie per convertire una sequenza nell'altra. Ebbene, per questi problemi apparentemente difficili sono invece stati trovati (spesso dopo dozzine di anni di lavoro) algoritmi capaci di risolverli in un tempo polinomiale (un tempo cioe' che cresce "solo" come n ad una qualche potenza). Come possiamo distinguere, dunque, i problemi davvero difficili da quelli che semplicemente sembrano difficili?
Ebbene, uno dei risultati fondamentali della teoria di NP-completezza sviluppata nei primi anni 70 da Cook, Karp e Levin e' proprio il seguente: e' possibile dimostrare, per la maggior parte dei problemi "difficili", che essi rappresentano problemi della stessa difficolta'. Se fossimo in grado, cioe', di risolvere in tempo polinomiale uno solo di questi problemi, allora saremmo automaticamente in grado di fornire un algoritmo polinomiale anche per ciascuno degli altri problemi. Proprio come se ciascuno di essi fosse in realta' nient'altro che la riformulazione di un solo stesso problema.