NP-Intermedio

Da Wikipedia, l'enciclopedia libera.
Se riscontri problemi nella visualizzazione dei caratteri, clicca qui.

La classe NPI[modifica | modifica sorgente]

I problemi NP-intermedi sono dei problemi di classe NP che non sono NP-completi, ossia:

NPI = NP \ (P ∪ NPC)

Nella Teoria della complessità computazionale siamo certi dell'esistenza delle classi P, NP e NP-C. Un'altra dibattito aperto è quello sulla presenza o meno di qualche altra classe di problemi in NP, ossia i problemi NP-intermedi (NPI).

Il teorema di Ladner dimostra che, se P≠NP, esistono dei problemi in NPI. Ovviamente è vero anche il contrario: se P=NP non esistono. La dimostrazione del teorema di Ladner è costruttiva, cioè mostra un problema che è in NPI. Esso non è pero' naturale. Non è ancora stato dimostrato che esistano dei problemi "naturali" in NPI, ed è tuttora un interrogativo aperto.

I candidati ad essere problemi di tipo NPI sono quei problemi di classe NP per i quali ancora non si è riusciti a provare che sono NPC.

Un tipico esempio di problema candidato ad essere NPI è il problema dell'isomorfismo dei grafi. Altri candidati ad essere NPI sono i problemi radi.