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.
No comments:
Post a Comment