Теория сложности
Раздел информатики, классифицирующий задачи по требуемому времени и памяти, а не по тому, насколько они трудными кажутся.
Область оформили Юрис Хартманис и Ричард Стирнс в 1965 году — они дали ей название и в 1993-м получили за неё премию Тьюринга. Задачи делятся на классы: P — решаемые за полиномиальное время, NP — те, чьё решение можно проверить за полиномиальное время, PSPACE — те, что укладываются в полиномиальную память независимо от времени. Классификация описывает задачу, а не конкретную реализацию, — этим она и отличается от O-нотации.
Практическая польза — знать, когда пора остановиться. Если задача NP-полная, искать точный эффективный алгоритм бессмысленно: надо переходить к эвристикам, приближениям или более узкой постановке. Криптография живёт ставкой на обратное: криптография с открытым ключом целиком держится на том, что никто не нашёл быстрого способа разложения больших чисел на множители.