Вычислительная сложность

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

История

Истоки теории вычислительной сложности восходят к 1930-м годам, когда Алонзо Чёрч и Алан Тьюринг заложили основы теории вычислимости. Однако систематическое изучение сложности началось в 1960-х годах, когда стало ясно, что не все вычислимые задачи решаются за практически приемлемое время. В 1965 году Юрий Матиясевич доказал неразрешимость десятой проблемы Гильберта, что подчеркнуло границы алгоритмических методов. В 1971 году Стивен Кук ввёл понятие NP-полноты, а в 1972 году Ричард Карп показал, что множество комбинаторных задач являются NP-полными. В 1970-х годах Леонид Левин независимо разработал аналогичные идеи. В 1990-х годах появились теории сложности для интерактивных доказательств и квантовых вычислений, а в 2000-х — для потоковых и распределённых систем.

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

Ресурсы и модели вычислений

Вычислительная сложность рассматривает два основных ресурса:

• Время — количество элементарных шагов (операций), выполняемых алгоритмом.
• Память — объём ячеек (битов, байтов), используемых в процессе вычисления.

Для оценки сложности используется модель вычислений, чаще всего — машина Тьюринга (одноленточная, многоленточная) или модель RAM (Random Access Machine), где доступ к памяти происходит за константное время.

Асимптотическая оценка

Сложность выражается через асимптотические обозначения, показывающие скорость роста функции от размера входных данных \(n\):

• O-большое (\(O(f(n))\)) — верхняя граница: не более чем \(f(n)\) с точностью до константы.
• Ω-большое (\(\Omega(f(n))\)) — нижняя граница: не менее чем \(f(n)\).
• Θ-большое (\(\Theta(f(n))\)) — точная оценка: одновременно \(O\) и \(\Omega\).
• o-малое (\(o(f(n))\)) — строго меньше, чем \(f(n)\), при больших \(n\).

Примеры: \(O(n^2)\) для пузырьковой сортировки, \(O(n \log n)\) для быстрой сортировки в среднем, \(O(2^n)\) для полного перебора.

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

Задачи делятся на классы в зависимости от ресурсных ограничений. Основные классы:

Класс P

P (polynomial time) — множество задач, которые могут быть решены за полиномиальное время на детерминированной машине Тьюринга. Примеры: сортировка массива, поиск кратчайшего пути в графе (алгоритм Дейкстры), проверка простоты числа (тест АКС). Задачи из P считаются «эффективно решаемыми».

Класс NP

NP (nondeterministic polynomial time) — множество задач, для которых решение можно проверить за полиномиальное время на детерминированной машине Тьюринга. Иначе говоря, если дать предполагаемый ответ, его корректность проверяется быстро. Примеры: задача коммивояжёра (найти маршрут длиной не более \(k\)), задача о выполнимости булевых формул (SAT), задача о рюкзаке. Вопрос, совпадает ли P с NP, остаётся открытым (проблема P vs NP).

NP-полные задачи

Задача называется NP-полной, если она принадлежит NP и к ней можно свести любую другую задачу из NP за полиномиальное время. Если для какой-то NP-полной задачи найдётся полиномиальный алгоритм, то все задачи из NP будут решаться за полиномиальное время. Примеры: SAT, задача о клике, задача о вершинном покрытии, задача о гамильтоновом цикле.

Класс EXP

EXP (exponential time) — задачи, решаемые за экспоненциальное время. Включает NP и более сложные задачи, например, проверку эквивалентности двух регулярных выражений.

Класс PSPACE

PSPACE — задачи, решаемые с использованием полиномиального объёма памяти. Включает P, NP, а также задачи, требующие экспоненциального времени, но полиномиальной памяти (например, игра Го на доске \(n \times n\)).

Класс BPP

BPP (bounded-error probabilistic polynomial time) — задачи, решаемые вероятностными алгоритмами за полиномиальное время с вероятностью ошибки не более 1/3. Пример: проверка простоты числа (тест Миллера — Рабина).

Класс QMA

QMA (quantum Merlin-Arthur) — квантовый аналог NP, где доказательство представляется в виде квантового состояния, а проверка выполняется квантовым компьютером.

Сложность в среднем и в худшем случае

Различают два подхода к оценке:

• Сложность в худшем случае — максимальное время/память для всех входов размера \(n\). Используется для гарантий производительности.
• Сложность в среднем случае — среднее время/память по всем входам, часто с учётом распределения вероятностей. Важна для криптографии, где требуется, чтобы задача была сложна в среднем.

Сложность задач и алгоритмов

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

Сведение задач

Сведение — это преобразование одной задачи в другую, сохраняющее ответ. Если задача \(A\) сводится к задаче \(B\) за полиномиальное время, то сложность \(A\) не превосходит сложности \(B\). Сведения используются для доказательства NP-полноты: если задача \(A\) сводится к \(B\) и \(A\) NP-полна, то \(B\) также NP-полна.

Применение

Теория вычислительной сложности применяется в:

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

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

• Проблема P vs NP входит в список «Задач тысячелетия» Математического института Клэя; за её решение назначена премия в 1 миллион долларов США.
• Существуют задачи, неразрешимые в принципе (например, проблема остановки), но их сложность не рассматривается в рамках теории вычислительной сложности, так как они не являются алгоритмически разрешимыми.
• Квантовые компьютеры могут решать некоторые задачи (например, факторизацию) за полиномиальное время, что ставит под вопрос стойкость современных криптосистем.

Источники

• Ахо А., Хопкрофт Дж., Ульман Дж. — «Построение и анализ вычислительных алгоритмов»
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. — «Алгоритмы: построение и анализ»
• Стивен Кук — «The Complexity of Theorem-Proving Procedures» (1971)
• Ричард Карп — «Reducibility Among Combinatorial Problems» (1972)
• Юрий Матиясевич — «Десятая проблема Гильберта» (1970)
• Michael Sipser — «Introduction to the Theory of Computation»