title: NP-Intermedio
text: # 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.
  
  