Введение

Класс задач, разрешимых за полиномиальное время. В теории вычислительной сложности, P, также известный как PTIME или DTIME(nO(1)), является фундаментальным классом сложности. Он включает в себя все задачи принятия решений, которые могут быть решены детерминированной машиной Тьюринга за полиномиальное количество времени вычислений, или полиномиальное время. Тезис Кобэма утверждает, что P – это класс вычислительных задач, которые являются "эффективно разрешимыми" или "практически решаемыми". Это не совсем точно: на практике некоторые задачи, не известные как принадлежащие классу P, имеют практические решения, а некоторые задачи, принадлежащие классу P, – нет, но это полезное эмпирическое правило.

Заметные проблемы в П

Известно, что класс P содержит множество естественных задач, включая задачи принятия решений для линейного программирования и нахождение максимального паросочетания. В 2002 году было доказано, что задача определения, является ли число простым, принадлежит классу P. Соответствующий класс задач, возвращающих значение, – FP. Для P полными являются несколько естественных задач, в том числе задача st-связности (или достижимости) на чередующихся графах. В статье, посвященной P-полным задачам, перечислены другие релевантные задачи из P.

Отношения с другими классами

Обобщением P является NP, класс задач принятия решений, разрешимых недетерминированной машиной Тьюринга за полиномиальное время. Эквивалентно, это класс задач принятия решений, для каждой "да"-инстанции которых существует полиномиальный по размеру сертификат, и этот сертификат может быть проверен детерминированной машиной Тьюринга за полиномиальное время. Класс задач, для которых это верно для "нет"-инстанций, называется co NP. P тривиально является подмножеством NP и co NP; большинство экспертов полагают, что это собственное подмножество, хотя это предположение (гипотеза) остается недоказанным. Другая открытая проблема заключается в том, верно ли NP = co NP; поскольку P = co P, отрицательный ответ означал бы, что P также, как известно, не меньше, чем L, класс задач, разрешимых с использованием логарифмического объема памяти. Машина, использующая пространство, не может использовать больше времени, чем это пространство, поскольку это общее количество возможных конфигураций; следовательно, L является подмножеством P. Другая важная проблема – верно ли L = P. Мы знаем, что P = AL, множество задач, разрешимых в логарифмической памяти с помощью чередующихся машин Тьюринга. Также известно, что P не больше PSPACE, класса задач, разрешимых в полиномиальном пространстве. Вопрос о том, верно ли P = PSPACE, также остается открытым. Подводя итог:

Здесь EXPTIME – это класс задач, разрешимых за экспоненциальное время. Из всех классов, представленных выше, известны только два строгих включения:

P строго включен в EXPTIME. Следовательно, все EXPTIME-трудные задачи лежат вне P, и по крайней мере одно из включений справа от P выше является строгим (на самом деле, широко распространено мнение, что все три строгие). L строго включен в PSPACE. Самые сложные задачи в P – это P-полные задачи. Другим обобщением P является P/poly, или Неоднородное полиномиальное время. Если задача находится в P/poly, то она может быть решена детерминированной машиной за полиномиальное время, при условии, что ей предоставлена строка подсказок, зависящая только от длины входных данных. Однако, в отличие от NP, полиномиальной машине не нужно обнаруживать поддельные строки подсказок; она не является верификатором. P/poly – это большой класс, содержащий почти все практически значимые задачи, включая все задачи из BPP. Если он содержит NP, то полиномиальная иерархия схлопывается до второго уровня. С другой стороны, он также содержит некоторые непрактичные задачи, включая некоторые неразрешимые задачи, такие как унарная версия любой неразрешимой задачи. В 1999 году Джин И Цай и Д. Сивакумар, опираясь на работы Мицунори Огихары, показали, что если существует разреженный язык, являющийся P-полным, то L = P.

P содержится в BQP, но неизвестно, является ли это включение строгим.

Свойства

Алгоритмы полиномиального времени замкнуты относительно композиции. Интуитивно это означает, что если записать функцию, время работы которой полиномиально, при условии, что вызовы функций занимают константное время, и если эти вызываемые функции сами требуют полиномиального времени, то весь алгоритм будет выполняться за полиномиальное время. Одним из следствий этого является то, что класс P является низким для себя. Это также одна из основных причин, по которой P считается классом, не зависящим от модели вычислений; любая "возможность" машины, такая как произвольный доступ к памяти, которую можно смоделировать за полиномиальное время, может быть просто скомпонована с основным полиномиальным алгоритмом, чтобы свести задачу к полиномиальному алгоритму на более простой машине. Классы языков, принадлежащих P, также замкнуты относительно обращения, пересечения, объединения, конкатенации, замыкания Клине, обратного гомоморфизма и дополнения.

Чистое доказательство существования алгоритмов в полиномиальном времени

Известно, что некоторые задачи разрешимы за полиномиальное время, но конкретный алгоритм для их решения неизвестен. Например, теорема Робертсона — Сеймура гарантирует существование конечного списка запрещенных миноров, характеризующих (например) множество графов, которые могут быть вложены на тор; более того, Робертсон и Сеймур показали, что существует алгоритм со сложностью O(n³) для определения, является ли данный граф минором для другого заданного графа. Это даёт неконструктивное доказательство существования полиномиального алгоритма для определения, может ли заданный граф быть вложен на тор, несмотря на отсутствие известного конкретного алгоритма для этой задачи.

Альтернативные характеристики

В описательной сложности класс P можно определить как задачи, выразимые в FO(LFP) – логике первого порядка с добавленным оператором наименьшей неподвижной точки – на упорядоченных структурах. В учебнике 1999 года по описательной сложности Иммерман приписывает этот результат Варди и самому себе. В 2001 году было опубликовано, что PTIME соответствует (положительным) грамматикам конкатенации диапазонов. Класс P также можно определить как класс алгоритмической сложности для задач, которые не являются задачами принятия решения (хотя, например, нахождение решения для экземпляра 2-удовлетворимости за полиномиальное время автоматически дает полиномиальный алгоритм для соответствующей задачи принятия решения). В этом случае P не является подмножеством NP, но P ∩ DEC является таковым, где DEC – это класс задач принятия решения.

История

Козен утверждает, что Кобэму и Эдмондсу "обычно приписывают изобретение понятия полиномиального времени". Кобхэм ввёл этот класс как надёжный способ характеризации эффективных алгоритмов, что и послужило основой для его диссертации. Однако, Х. К. Поклинтон в статье 1910 года проанализировал два алгоритма для решения квадратных сравнений и отметил, что один из них требовал времени "пропорционального степени логарифма модуля", а другой – времени, пропорционального "самому модулю или его квадратному корню", тем самым явно разграничивая алгоритмы, работающие за полиномиальное время, и те, которые не работали за полиномиальное время.