P (karmaşıklık)

P, çokterimli zamanda (belirlenimli Turing Makinesi ile) çözülebilen karar problemlerini içeren karmaşıklık sınıfıdır. P sınıfı pek çok doğal problemi içerse de bazı önemli problemlerin (bk. NP) P içerisine girip girmediği bilinmemektedir.

P sınıfı örnekleri 
 Doğrusal programlama
 Eşleştirme problemleri
 Asallık testi
 İkili arama

İlgili bağlantılar 
 P ile NP arasındaki ilişki
 Polinomsal zaman

Karmaşıklık sınıfları