Back NP-intermediate English NP-intermédiaire French NP ביניים HE Problem NP-pośredni Polish NP-Intermediário Portuguese
I problemi NP-intermedi sono dei problemi di classe NP - P che non sono NP-completi, ossia:
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.
