P ve NP: bir problem ne kadar zordur?

Kısaca: Problemlerin bir sınıflandırması: P çabuk çözülebilenlerdir; NP’de önerilen bir çözüm çabuk denetlenebilir, çabuk bulunup bulunamayacağı ise açıktır.

Biraz daha ayrıntılı: Karmaşıklık kuramı, çabanın girdi boyutuyla ne kadar güçlü arttığını sorar. Burada “hızlı”, en çok polinom demektir; yani kabaca n², n³ (n girdi boyutudur). 2ⁿ (“üstel”) gibi bir çaba o kadar güçlü büyür ki orta girdiler bile pratikte çözülemez hale gelir.