Система обозначений О (), которая в наши дни широко используется в компьютерных науках, была впервые определена в контексте теории чисел немецким математиком П.Г. Н. Бахманом [57]. Понятие NP-полноты было предложено Куком [289], а современный метод определения способа сведения одной проблемы к другой предложен Карпом [772]. И Кук, и Карп получили за свою работу премию Тьюринга — высшую награду в компьютерных науках.

В число классических работ по анализу и проектированию алгоритмов по праву входят [8] и [809]; более современные достижения отражены в [295] и [1489]. Эти книги в основном посвящены проектированию и анализу алгоритмов решения разрешимых задач. Сведения в области теории NP-полноты и других форм неразрешимости приведены в книгах Гэри и Джонсона [520], а также Пападимитриу [1168]. В своей книге Гэри и Джонсон не только изложили теоретические основы, но и привели примеры, наглядно показывающие, по каким причинам специалисты в области компьютерных наук считают бесспорным утверждение, что линии водораздела между разрешимыми и неразрешимыми задачами проходит по границе между полиномиальной и экспоненциальной временной сложностью. Кроме того, эти ученые представили объемистый каталог задач, известных как NP-полные или неразрешимые по каким-то другим критериям.

К числу хороших учебников по теории вероятностей относятся [122], [254], [463] и [1310].