Каких ресурсов требует решение вычислительной задачи
Теория вычислительной сложности изучает ресурсы, необходимые для решения задач, прежде всего время и память. Класс NP включает задачи распознавания с полиномиальной проверкой свидетельства положительного ответа; принадлежность к NP сама по себе не доказывает неполиномиальную трудность.
Теория сложности
Классы сложности
P — решаемо за полиномиальное время. NP — проверка за полином. NP-полные — "самые сложные" в NP (SAT, TSP). Проблема P vs NP — открыта с 1971.
O-нотация и асимптотика
O(f) — верхняя граница роста, Ω(f) — нижняя, Θ(f) — точная. O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ). Оценка алгоритмов по времени и памяти.
NP-полнота
Задача NP-полна если в NP и любая NP-задача сводится к ней за полином. Теорема Кука (1971): SAT — NP-полна. Тысячи NP-полных задач. Решение одной → решение всех.