Класс P

Класс P (от англ. polynomial time — полиномиальное время) — это множество задач разрешимости (decision problems) в теории алгоритмов, для которых существует детерминированный алгоритм, решающий задачу за время, ограниченное полиномиальной функцией от длины входных данных. Формально, задача принадлежит классу P, если существует константа \(c\) и детерминированная машина Тьюринга, которая для любого входа длины \(n\) вычисляет ответ за время \(O(n^c)\). Класс P является фундаментальным понятием теории сложности вычислений и считается формальным аналогом класса «практически разрешимых» задач.

Определение и формальная модель

Класс P определяется в рамках модели детерминированной машины Тьюринга (ДМТ) с одной или несколькими лентами. Задача разрешимости \(L\) (подмножество всех бинарных строк \(\{0,1\}^*\)) принадлежит P, если существует ДМТ \(M\) и полином \(p(n)\) такие, что для любой входной строки \(x\) длины \(n\):

• \(M\) останавливается на входе \(x\) за не более чем \(p(n)\) шагов;
• если \(x \in L\), то \(M\) выдаёт «да» (1);
• если \(x \notin L\), то \(M\) выдаёт «нет» (0).

Полиномиальная временная сложность не зависит от конкретной модели вычислений: класс P остаётся инвариантным при переходе между детерминированными машинами Тьюринга, RAM-машинами, реальными компьютерами (с точностью до полиномиального множителя). Это свойство известно как тезис Чёрча — Тьюринга для полиномиального времени.

История и значение

Понятие класса P было введено в 1960-х годах в работах Алана Кобэма (Alan Cobham) и Джека Эдмондса (Jack Edmonds). Кобэм в 1964 году сформулировал тезис, согласно которому задача считается «практически разрешимой», если она решается за полиномиальное время. Эдмондс в 1965 году ввёл термин «полиномиальный алгоритм» для задачи о паросочетаниях. В 1971 году Стивен Кук (Stephen Cook) в своей знаменитой работе «The Complexity of Theorem-Proving Procedures» формализовал класс P и поставил проблему равенства P и NP.

Класс P является центральным в теории сложности, поскольку он определяет границу между задачами, которые можно эффективно решить на компьютере, и теми, которые требуют экспоненциального времени (по крайней мере в худшем случае). Однако на практике полиномиальные алгоритмы с высокой степенью (например, \(O(n^{100})\)) могут быть неэффективными, а некоторые экспоненциальные алгоритмы — вполне применимыми для небольших входных данных.

Примеры задач из класса P

Арифметика и алгебра

• Умножение двух целых чисел — алгоритмы школьного умножения (\(O(n^2)\)), Карацубы (\(O(n^{1.585})\)), Шёнхаге — Штрассена (\(O(n \log n \log \log n)\)).
• Проверка простоты числа — тест Миллера — Рабина (вероятностный, но детерминированный вариант AKS (2002) работает за полиномиальное время).
• Решение системы линейных уравнений — метод Гаусса (\(O(n^3)\)).

Теория графов

• Проверка связности графа — поиск в ширину или глубину (\(O(n+m)\)).
• Поиск кратчайшего пути — алгоритм Дейкстры (\(O(m + n \log n)\)), алгоритм Беллмана — Форда (\(O(nm)\)).
• Поиск минимального остовного дерева — алгоритмы Прима и Краскала (\(O(m \log n)\)).
• Проверка двудольности графа — обход с раскраской (\(O(n+m)\)).

Логика и комбинаторика

• Проверка выполнимости 2-КНФ (2-SAT) — сводится к поиску сильно связных компонент в графе импликаций (\(O(n+m)\)).
• Задача о назначениях — венгерский алгоритм (\(O(n^3)\)).
• Вычисление определителя матрицы — метод Гаусса (\(O(n^3)\)).

Динамическое программирование

• Задача о рюкзаке (0-1) — в случае, когда веса и стоимости ограничены полиномиально, решается за псевдополиномиальное время (\(O(nW)\)), что не является полиномиальным относительно длины входа, но для фиксированного \(W\) — да.
• Вычисление чисел Фибоначчи — матричное возведение в степень (\(O(\log n)\)).

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

P и NP

Класс NP (Nondeterministic Polynomial time) включает задачи, для которых ответ «да» можно проверить за полиномиальное время на детерминированной машине. Очевидно, что \(P \subseteq NP\). Вопрос о том, совпадают ли P и NP (проблема P vs NP), является одной из семи «задач тысячелетия» Математического института Клэя (Clay Mathematics Institute). Большинство специалистов полагает, что \(P \neq NP\), однако строгого доказательства не существует. Если \(P = NP\), то многие практически важные задачи (например, задача коммивояжёра, криптоанализ) станут разрешимыми за полиномиальное время, что приведёт к революции в информатике и криптографии.

P и co-NP

Класс co-NP состоит из задач, для которых ответ «нет» можно проверить за полиномиальное время. Известно, что \(P \subseteq NP \cap co\text{-}NP\). Если \(P \neq NP\), то \(P \subset NP \cap co\text{-}NP\) (строгое включение). Пример задачи, лежащей в \(NP \cap co\text{-}NP\), но не известной как полиномиальная: разложение числа на множители.

P и PSPACE

Класс PSPACE включает задачи, разрешимые с полиномиальным объёмом памяти (время может быть экспоненциальным). Известно, что \(P \subseteq PSPACE\). Считается, что \(P \subset PSPACE\) (строгое включение), но это также не доказано.

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

Задача называется P-полной, если она принадлежит P и любая другая задача из P может быть сведена к ней за логарифмическое пространство (или за полиномиальное время с ограниченной памятью). Примеры P-полных задач:

• Проверка выполнимости булевой схемы (Circuit Value Problem) — задача вычисления значения булевой схемы при заданных входах.
• Линейное программирование — задача нахождения оптимального решения системы линейных неравенств (доказано в 1979 году Хачияном).
• Достижимость в графе — задача проверки существования пути между двумя вершинами (для неориентированных графов — P-полна по логарифмическому пространству).

Критика и ограничения

Понятие класса P не является абсолютным критерием практической разрешимости. Полиномиальный алгоритм с высокой степенью (например, \(O(n^{100})\)) может быть неприменим на практике, в то время как экспоненциальный алгоритм с хорошей эвристикой может работать быстро для типичных входных данных. Кроме того, класс P не учитывает константы и скрытые факторы (например, размер используемой памяти). В реальных вычислениях важны также классы сложности с низкими полиномиальными степенями (например, \(O(n^2)\) или \(O(n \log n)\)).

Другое ограничение связано с тем, что класс P определён для детерминированных машин Тьюринга, которые не учитывают параллельные вычисления, квантовые вычисления или вероятностные алгоритмы. Для квантовых компьютеров существует класс BQP (Bounded-error Quantum Polynomial time), который, как полагают, шире P, но не включает NP.

Открытые проблемы

• P vs NP — основная нерешённая проблема теории сложности.
• P vs PSPACE — неизвестно, совпадают ли эти классы.
• P vs BPP — класс BPP (вероятностные алгоритмы с ограниченной ошибкой) предположительно равен P (тезис Дерзовица — Гольдрейха), но строго не доказано.
• Существование односторонних функций — если \(P \neq NP\), то существуют функции, которые легко вычислить, но трудно обратить, что лежит в основе криптографии.

Применение в информатике

Класс P является основой для классификации алгоритмов и задач в таких областях, как:

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

Источники

• Arora, S., & Barak, B. (2009). Computational Complexity: A Modern Approach. Cambridge University Press.
• Sipser, M. (2013). Introduction to the Theory of Computation (3rd ed.). Cengage Learning.
• Papadimitriou, C. H. (1994). Computational Complexity. Addison-Wesley.
• Cook, S. A. (1971). «The complexity of theorem-proving procedures». Proceedings of the 3rd Annual ACM Symposium on Theory of Computing.
• Кобэм, А. (1964). «The intrinsic computational difficulty of functions». Logic, Methodology and Philosophy of Science.
• Эдмондс, Дж. (1965). «Paths, trees, and flowers». Canadian Journal of Mathematics.