Teoria złożoności obliczeniowej
Dział informatyki, który klasyfikuje problemy według czasu i pamięci, jakich wymagają — a nie według tego, jak trudne się wydają.
Dziedzinę sformalizowali w 1965 roku Juris Hartmanis i Richard Stearns, którzy ją nazwali i za to otrzymali w 1993 roku Nagrodę Turinga. Problemy dzielą się na klasy: P to te, które da się rozwiązać w czasie wielomianowym, NP to te, których rozwiązanie da się zweryfikować w czasie wielomianowym, mając kandydata na odpowiedź, a PSPACE to te, które mieszczą się w pamięci wielomianowej bez względu na czas. Klasyfikacja opisuje problem, a nie konkretną implementację — i właśnie tym różni się od notacji dużego O.
Praktyczna wartość tej teorii polega na tym, że wiadomo, kiedy przestać szukać. Jeśli problem jest NP-zupełny, poszukiwanie dokładnego, wydajnego algorytmu to strata czasu; zostają heurystyki, aproksymacje albo zawężona wersja problemu. Kryptografia opiera się na zakładzie odwrotnym: kryptografia klucza publicznego stoi wyłącznie na tym, że nikt nie znalazł szybkiego sposobu faktoryzacji dużych liczb.