NP-Intermedio

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

$NPI=NP\setminus (P\cup 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 è però 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 - P 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.