NP-orta

Olarak karmaşıklık teorisi , bir sorun NP-aracılığıyla bir sorun NP ne olduğu, NP-tam ne de P . NP-ara problemler sınıfı NPI ile belirtilir . Richard Emil Ladner, 1975'te P ≠ NP , NPI'nin boş olmadığı varsayımı altında , bunun Ladner teoremi olduğunu gösterdi .

Tarih

Gösteriler için fikirler

Notlar ve referanslar

1. Richard E. Ladner , "  Polinom Zaman Azaltılabilirliğinin Yapısı Üzerine  ", Journal of the ACM , cilt.  22, n o  1,Ocak 1975, s.  155–171 ( DOI  10.1145 / 321864.321877 , çevrimiçi okuma , 16 Temmuz 2017'de erişildi ).