Karmaşıklık kuramı
Bilgisayar biliminin, problemleri ne kadar zor hissettirdiklerine göre değil, ne kadar zaman ve bellek istediklerine göre sınıflandıran dalı.
Alan, 1965'te Juris Hartmanis ve Richard Stearns tarafından biçimlendirildi; adını onlar koydu, bu çalışmayla 1993 Turing Ödülü'nü de aldılar. Problemler sınıflara ayrılır: P polinom zamanda çözülebilenler, NP aday bir çözümün polinom zamanda doğrulanabildiği problemler, PSPACE ise zamandan bağımsız olarak polinom bellekle çözülebilenlerdir. Sınıflandırma tek bir gerçekleştirmeyi değil problemin kendisini tanımlar; Big-O'dan ayrıldığı nokta da budur.
Pratik değeri, nerede pes edileceğini bilmektir. Bir problem NP-tam ise tam ve verimli bir algoritma aramak boşa emektir; çıkış yolu sezgisel yöntemler, yaklaşık çözümler ya da problemin daha dar bir sürümüdür. Kriptografi ise tam tersi bahisle yaşar: açık anahtarlı kriptografi, büyük sayıları çarpanlarına ayırmanın hızlı bir yolunu henüz kimsenin bulamamış olmasına dayanır.