problemi P e NP
problemi P e NP
problemi P e NP classi di problemi costituite sulla base della loro → complessità computazionale, cioè della intrinseca difficoltà della loro risoluzione. Un problema appartiene alla classe di complessità P, ed è spesso detto problema P, se esiste un algoritmo di soluzione dotato di complessità polinomiale, ossia se il tempo di risoluzione è una funzione polinomiale delle dimensioni dei valori in input; questo accade se l’algoritmo risolutivo ha una complessità di calcolo dell’ordine O(nα), con α > 0. L’appartenenza di un problema alla classe P può essere sinonimo di facilità di risoluzione solo se l’esponente α ha un valore sufficientemente piccolo. È evidente, per esempio, che un algoritmo di complessità O(n13) è polinomiale, ma prevede comunque un costo in termini di tempo di calcolo non trascurabile. Un problema appartiene alla classe di complessità NP, e viene chiamato semplicemente problema NP, se, posto in una qualsiasi forma di riconoscimento o di decisione, è verificabile in tempo polinomiale. Non si tratta perciò di decidere in tempo polinomiale se l’istanza è affermativa o meno, ma di verificare il problema in tempo polinomiale, data un’istanza affermativa del problema. L’appartenenza alla classe NP appare, quindi, meno riduttiva dell’appartenenza a P; infatti, affinché un problema sia in NP non è necessario che sia risolubile in tempo polinomiale, ma solo che, se l’istanza è affermativa, esso sia verificabile in tempo polinomiale. Al contrario, è certo che se un problema è polinomiale allora appartiene a NP. Infatti, considerando un’istanza affermativa di un problema P, è sufficiente usare l’algoritmo polinomiale di risoluzione, che richiede una complessità polinomiale, verificando che alla fine produrrà la risposta affermativa. Quindi: P ⊆ NP.
L’inclusione opposta, e dunque la possibile equivalenza tra le classi di complessità P e NP, è di estrema rilevanza, tanto da essere stata inclusa nel 2000 fra i → problemi del millennio, i sette più importanti problemi matematici irrisolti. La classe NP riveste un’importanza notevole poiché appartengono a essa la maggior parte dei problemi di riconoscimento, decisione o ottimizzazione (per es. l’ordinamento di un insieme di elementi, l’imballaggio di oggetti in contenitori, la struttura dei circuiti elettronici e delle reti telefoniche, la ricerca di itinerari ottimali, la costruzione di orari scolastici ecc.). La richiesta per cui, una volta calcolata la soluzione di un problema, si possa stabilire attraverso una verifica polinomiale se essa soddisfi le proprietà del problema, appare senza dubbio molto ragionevole e rispondente alle necessità di ricerca mediante calcoli più semplici possibili. Occorre precisare infine che non tutti i problemi esistenti appartengono a NP, esistendo altre classi di problemi, il cui significato e interesse è tuttavia teorico piuttosto che pratico. Un particolare gruppo della classe NP è costituito dai problemi NP-completi, accomunati dalla caratteristica che la soluzione di uno qualsiasi di questi problemi garantirebbe la risolubilità di tutti i problemi NP. In questa sottoclasse rientra anche il celebre problema del → commesso viaggiatore che deve visitare un certo numero di città, ciascuna una volta sola e senza mai tornare indietro, attraverso un percorso di lunghezza minima. Sebbene le classi di tipo NP non siano le più complesse, esse contengono alcuni tra i problemi al momento di maggior interesse, tra cui quello della fattorizzazione di un numero, la cui soluzione permetterebbe di decrittare alcuni dei più importanti sistemi di crittografia in uso.