Теория сложности вычислений

Теория сложности вычислений — это раздел теоретической информатики и математики, изучающий ресурсы, необходимые для решения вычислительных задач. Основными ресурсами являются время (количество элементарных операций) и память (объём используемой ячейки). Теория сложности классифицирует задачи по классам в зависимости от того, как быстро растут требования к ресурсам с увеличением размера входных данных.

Основные понятия

Теория сложности оперирует несколькими фундаментальными понятиями.

Вычислительная задача

В контексте теории сложности под задачей понимается абстрактная проблема, для которой существует множество возможных входов (инстанций) и множество возможных выходов. Например, задача сортировки: вход — неупорядоченный список чисел, выход — тот же список, отсортированный по возрастанию. Задача может быть массовой (решается для всех возможных входов) или индивидуальной (решается для конкретного набора данных).

Размер входа

Размер входа (обозначается \( n \)) — это количество бит или символов, необходимых для кодирования входных данных. Для задачи о сумме подмножества размер входа — это количество чисел в множестве и их битовая длина. Рост сложности оценивается как функция от \( n \).

Асимптотическая оценка (O-нотация)

Для описания скорости роста сложности используется О-большое (Big O). Она позволяет игнорировать константные множители и младшие члены, фокусируясь на поведении функции при больших \( n \). Например:

• \( O(1) \) — константная сложность (не зависит от размера входа).
• \( O(\log n) \) — логарифмическая сложность (например, бинарный поиск).
• \( O(n) \) — линейная сложность (например, поиск максимума).
• \( O(n^2) \) — квадратичная сложность (например, пузырьковая сортировка).
• \( O(2^n) \) — экспоненциальная сложность (например, перебор всех подмножеств).

Классы сложности

Задачи группируются в классы по типу используемой вычислительной модели и по ограничениям на ресурсы.

Класс P (Polynomial time)

Класс P включает задачи, которые могут быть решены за полиномиальное время на детерминированной машине Тьюринга (или на обычном компьютере). Формально: существует алгоритм, время работы которого \( O(n^k) \) для некоторой константы \( k \). Класс P считается классом «практически разрешимых» задач. Примеры: проверка числа на простоту (алгоритм AKS), поиск кратчайшего пути в графе (алгоритм Дейкстры), умножение матриц.

Класс NP (Nondeterministic Polynomial time)

Класс NP включает задачи, для которых решение может быть проверено за полиномиальное время, если предоставлено «свидетельство» (сертификат). Формально: существует недетерминированная машина Тьюринга, которая решает задачу за полиномиальное время. Класс NP включает все задачи из P, а также множество задач, для которых эффективный алгоритм решения неизвестен. Примеры: задача выполнимости булевых формул (SAT), задача коммивояжёра (TSP), задача о рюкзаке.

Класс NP-полные (NP-complete)

NP-полные задачи — это «самые сложные» задачи в классе NP. Если для какой-либо NP-полной задачи будет найден полиномиальный алгоритм, то все задачи из NP будут решаться за полиномиальное время. Ключевое свойство: любая задача из NP может быть сведена к данной NP-полной задаче за полиномиальное время (полиномиальная сводимость по Карпу). Первой NP-полной задачей была доказана задача SAT (теорема Кука — Левина, 1971). Другие примеры: задача о клике, задача о вершинном покрытии, задача о гамильтоновом цикле.

Класс PSPACE

Класс PSPACE включает задачи, которые могут быть решены с использованием полиномиального объёма памяти (время при этом может быть экспоненциальным). Считается, что \( P \subseteq NP \subseteq PSPACE \), но точные соотношения неизвестны. Примеры: задача проверки эквивалентности регулярных выражений, некоторые игры (например, «Го» на доске произвольного размера).

Класс BPP (Bounded-error Probabilistic Polynomial time)

Класс BPP включает задачи, решаемые за полиномиальное время вероятностными алгоритмами с вероятностью ошибки менее 1/3 (например, тест Миллера — Рабина на простоту). Считается, что \( P \subseteq BPP \), и многие специалисты полагают, что \( P = BPP \) (тезис о дерандомизации).

История развития

Теория сложности вычислений как самостоятельная дисциплина оформилась в 1960—1970-х годах.

Ранние работы (1960-е)

• Юрис Хартманис и Ричард Стернс (1965) ввели понятие временной и ёмкостной сложности, заложив основы теории.
• Мануэль Блюм (1967) сформулировал аксиомы сложности (теорема Блюма), показав, что существуют функции, не имеющие оптимального алгоритма.

Формализация классов (1970-е)

• Стивен Кук (1971) доказал, что задача SAT является NP-полной, предложив концепцию сводимости.
• Ричард Карп (1972) опубликовал список из 21 NP-полной задачи, включая задачу о рюкзаке, задачу о вершинном покрытии и задачу о клике.
• Леонид Левин (1973) независимо от Кука сформулировал аналогичную теорию в СССР, доказав NP-полноту задачи о выполнимости.

Современный этап (1980-е — настоящее время)

• Развитие теории интерактивных доказательств (IP = PSPACE, 1990).
• Доказательство того, что задача проверки простоты числа (PRIMES) лежит в P (Агравал, Кайал, Саксена, 2002).
• Исследование квантовых вычислений и классов BQP (квантовое полиномиальное время).

Проблема P vs NP

Центральная нерешённая проблема теории сложности — вопрос о равенстве классов P и NP. Если \( P = NP \), то для любой задачи, решение которой можно быстро проверить, существует и быстрый алгоритм решения. Это имело бы колоссальные последствия для криптографии, оптимизации, искусственного интеллекта. Большинство исследователей полагают, что \( P \neq NP \), но строгого доказательства не существует. Задача входит в список «Проблем тысячелетия» Института Клэя, за её решение назначена премия в 1 миллион долларов США.

Применение

Теория сложности находит практическое применение в нескольких областях:

• Криптография: стойкость многих криптосистем (например, RSA) основана на предположении, что задачи факторизации и дискретного логарифмирования не лежат в P.
• Оптимизация: NP-трудные задачи решаются приближёнными алгоритмами, эвристиками или методами ветвей и границ.
• Искусственный интеллект: многие задачи машинного обучения (например, обучение нейронных сетей) являются NP-трудными.
• Базы данных: задачи оптимизации запросов и проверки эквивалентности реляционных выражений относятся к классам сложности.

Интересные факты

• Существуют задачи, для которых доказано, что они требуют экспоненциального времени (например, задача о проверке эквивалентности двух регулярных выражений с дополнением).
• Класс EXPTIME включает задачи, решаемые за экспоненциальное время. Доказано, что \( P \neq EXPTIME \), то есть существуют задачи, принципиально не решаемые за полиномиальное время.
• В 2020 году российский математик Григорий Перельман (известный доказательством гипотезы Пуанкаре) также внёс вклад в теорию сложности, но его работа по NP-полноте задачи о распознавании трёхмерных многообразий остаётся неопубликованной.

Источники

• Ахо А., Хопкрофт Дж., Ульман Дж. «Построение и анализ вычислительных алгоритмов». — М.: Мир, 1979.
• Гэри М., Джонсон Д. «Вычислительные машины и труднорешаемые задачи». — М.: Мир, 1982.
• Стивен Кук. «The Complexity of Theorem-Proving Procedures» (1971).
• Ричард Карп. «Reducibility Among Combinatorial Problems» (1972).
• Хопкрофт Дж., Мотвани Р., Ульман Дж. «Введение в теорию автоматов, языков и вычислений». — М.: Вильямс, 2002.