П (сложность) - P (complexity)

В теории сложности вычислений , Р , также известный как PTIME или DTIME ( п O (1) ), является одним из основных классов сложности . Он содержит все проблемы принятия решений, которые могут быть решены детерминированной машиной Тьюринга с использованием полиномиального количества времени вычислений или полиномиального времени .

Тезис Кобэй считает , что Р является классом вычислительных задач, которые «эффективно разрешимы» или « послушными ». Это неточно: на практике некоторые проблемы, не относящиеся к P, имеют практические решения, а некоторые, которые находятся в P, нет, но это полезное эмпирическое правило .

Определение

Язык L в P , если и только если существует детерминированный машина Тьюринга M , такой , что

  • M работает за полиномиальное время на всех входах
  • Для всех х в L , М выходов 1
  • Для всех x, не входящих в L , M выводит 0

P также можно рассматривать как однородное семейство логических схем . Язык L принадлежит P тогда и только тогда, когда существует однородное за полиномиальное время семейство логических схем , такое что

  • Для всех , принимает п битов в качестве входных и выходных 1 бит
  • Для всех х в L ,
  • Для всех x не в L ,

Определение схемы можно ослабить, чтобы использовать только однородное семейство лог-пространства без изменения класса сложности.

Заметные проблемы в 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 сам по себе является низким . Это также одна из основных причин того, что P считается машинно-независимым классом; любая машинная «особенность», такая как произвольный доступ , которая может быть смоделирована за полиномиальное время, может быть просто скомбинирована с основным алгоритмом полиномиального времени, чтобы свести его к алгоритму полиномиального времени на более простой машине.

Языки в P также закрыты относительно обращения, пересечения , объединения , конкатенации , замыкания Клини , обратного гомоморфизма и дополнения .

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

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

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

С точки зрения описательной сложности P можно описать как проблемы, выражаемые в FO (LFP) , логике первого порядка с добавленным к ней оператором наименьшей фиксированной точки на упорядоченных структурах. В учебнике Иммермана по описательной сложности 1999 года Иммерман приписывает этот результат Варди и Иммерману.

В 2001 году было опубликовано, что PTIME соответствует (положительным) грамматикам конкатенации диапазонов .

История

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

Примечания

использованная литература

внешние ссылки