problemi NP-completi
problemi NP-completi
I problemi di decisione possono essere classificati prescindendo dall’algoritmo usato per risolverli. Sono state individuate le classi di problemi P, NP e NP-completi. Un problema è detto di classe P (polinomiale) se esiste un algoritmo che fornisce la risposta in tempo polinomiale rispetto alle dimensioni L del problema. Un problema è detto di classe NP se, data una possibile soluzione, esiste un algoritmo polinomiale nelle dimensioni L del problema in grado di verificare se questa è effettivamente soluzione del problema. Ovviamente la classe NP è più generale della classe P e la contiene. Dati ora due problemi R e Q, si dice che R si riduce a Q (e si indica con R μQ) se esiste un algoritmo polinomiale che associa a ogni istanza di R un’istanza di Q in modo tale che la soluzione dell’istanza di Q fornisce la soluzione della corrispondente istanza di R. Un problema R∈NP si dice NP-completo (o appartenente alla classe NP-completa) se QμR per ogni Q∈NP. In questo senso i problemi NP-completi sono i problemi più difficili della classe NP. Resta da stabilire se la classe NP è effettivamente più generale di P o se esse in realtà coincidono. Questa domanda è tuttora senza risposta: il problema se P=NP oppure no è uno dei maggiori problemi aperti nel settore algoritmico, tanto da essere incluso nel novero dei cosiddetti problemi del millennio. La congettura che viene comunemente accettata è che sia PfiNP. Da ciò seguirebbe che la classe P e la classe NP-completa non possono avere elementi comuni. Infatti, se un problema R è nella classe NP-completa, allora per definizione tutti i problemi in NP possono essere ridotti in tempo polinomiale a R; ma se R∈P, allora ciò proverebbe che P =NP in contrasto con la congettura. Ci si può chiedere allora se nella classe NP, oltre a problemi in P e nella classe NP-completa, ci siano altri problemi oppure no. Anche a questa domanda non vi è oggi una risposta; non sono noti problemi in NP per cui sia stato dimostrato (sulla base della congettura PfiNP) che non appartengono né a P né alla classe NP-completa, ma non è stato neppure dimostrato che non ve ne possano essere. Da un punto di vista operativo, per dimostrare che un problema R è nella classe NP-completa basta prendere un problema noto per essere in tale classe e costruire una riduzione da questo problema a R. A causa della transitività della riduzione ciò basta per affermare che anche R è NP-completo. Ciò ha come conseguenza applicativa che, qualora si presenti un problema R per cui viene proposto un algoritmo esponenziale, il tentativo naturale sarebbe quello di cercare un algoritmo migliore di tipo polinomiale. Questo tentativo può però essere privo di sbocco: se viene infatti dimostrato che il problema è NP-completo, è estremamente difficile che si possa trovare un algoritmo polinomiale (ciò equivarrebbe a dimostrare che P=NP). Quindi il suggerimento per il progettista di algoritmi è quello di fare alcuni tentativi per costruire un algoritmo polinomiale e, se questi falliscono, tentare di dimostrare la NP-completezza del problema. Nel caso in cui il problema sia NP-completo e l’algoritmo esponenziale non sia praticabile, sarà necessario ripiegare su tecniche euristiche che, nella migliore delle ipotesi, forniscono soluzioni approssimate. In genere si riescono a risolvere problemi polinomiali per dimensioni anche molto elevate mentre si riescono a risolvere problemi NP-completi in modo esatto solo in pochi casi di dimensioni non molto elevate. Esistono anche problemi al di fuori della classe NP (quindi più difficili da risolvere dei problemi in NP), ma si tratta in genere di problemi costruiti artificialmente, di scarso significato applicativo.