Hal ini ditunjukkan oleh Ladner bahwa jika P å NP kemudian ada masalah di NP yang tidak dalam P atau NP-lengkap. Masalah seperti itu disebut masalah menengah NP. Masalah isomorfisme grafik, masalah logetisme diskritma dan masalah faktorisasi integer adalah contoh dari masalah yang diyakini sebagai interemediate NP. Mereka adalah beberapa dari sangat sedikit masalah NP tidak dikenal berada di P atau menjadi NP-lengkap.
Apa empat contoh masalah yang diyakini sebagai NP=intermediate?
Masalah isomorfisme grafik, masalah logetisme diskritma dan masalah faktorisasi integer