П (сложность)

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

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

Определение

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

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

P также можно рассматривать как однородное семейство булевых схем . Язык L находится в P тогда и только тогда, когда существует однородное за полиномиальное время семейство булевых схем. $\{C_{n}:n\in \mathbb {N} \}$, такой, что

• Для всех $n\in \mathbb {N}$, $C_{n}$ принимает на вход n бит и выводит 1 бит
• Для всех x в L , $C_{|x|}(x)=1$
• Для всех x не из L , $C_{|x|}(x)=0$

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

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

Известно, что P содержит множество естественных задач, включая варианты решения линейного программирования и поиск максимального соответствия . В 2002 году было показано, что проблема определения того, является ли число простым, находится в P. Родственный класс функциональных задач — FP .

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

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

Представление связи между классами сложности

Включения классов сложности, включая P , NP , co-NP , BPP , P/poly , PH и PSPACE.

Обобщением P является NP , который представляет собой класс проблем решения , решаемых недетерминированной машиной Тьюринга , работающей за полиномиальное время . Эквивалентно, это класс задач принятия решений, где каждый экземпляр «да» имеет сертификат полиномиального размера, а сертификаты могут быть проверены с помощью детерминированной машины Тьюринга с полиномиальным временем. Класс задач, для которых это верно для экземпляров «нет», называется co-NP . P тривиально является подмножеством NP и co-NP; большинство экспертов считают, что это правильное подмножество, хотя это убеждение (т. ${\mathsf {P}}\subsetneq {\mathsf {NP}}$ гипотеза) остается недоказанной . Другая открытая проблема заключается в том, = NP = co-NP; поскольку P = co-P, отрицательный ответ будет означать ${\mathsf {P}}\subsetneq {\mathsf {NP}}$.

Также известно, что P не меньше L — класса задач, решаемых в логарифмическом объеме памяти . Решающее устройство, использующее $O(\log n)$ пространство не может использовать более $2^{O(\log n)}=n^{O(1)}$ время, ведь это общее количество возможных конфигураций; таким образом, L является подмножеством P. Другая важная проблема заключается в том, является ли L = P. Мы знаем, что P = AL, набор проблем, решаемых в логарифмической памяти с помощью чередующихся машин Тьюринга . Также известно, что P не превышает PSPACE — класса задач, разрешимых в полиномиальном пространстве. Опять же, является ли P = PSPACE открытой проблемой. Подводя итог:

${\mathsf {L}}\subseteq {\mathsf {AL}}={\mathsf {P}}\subseteq {\mathsf {NP}}\subseteq {\mathsf {PSPACE}}\subseteq {\mathsf {EXPTIME}}.$

Здесь 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 по отношению к классам вероятностной сложности ( ZPP , RP , co-RP, BPP , BQP , PP ), все в рамках PSPACE . Неизвестно, являются ли какие-либо из этих ограничений строгими.

P содержится в BQP , неизвестно, является ли содержание строгим.

Характеристики

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

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

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

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

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

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

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

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

История

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

Ссылки

• Эдмондс, Дж. (1965). «Дорожки, деревья и цветы». Канадская Дж. Математика . 17 : 449–467. дои : 10.4153/CJM-1965-045-4 .
• Кобэм, Алан (1965). «Внутренняя вычислительная сложность функций». Учеб. Логика, методология и философия науки II 1964 . Северная Голландия.
• Рабин, Майкл О. (1967). «Математическая теория автоматов». Математические аспекты информатики. Учеб. Симпозиумы 1966 года. Прил. Матем., Том. XIX . амер. Математика. Соц. стр. 153–175.
• Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стейн . Введение в алгоритмы , второе издание. MIT Press и МакГроу-Хилл, 2001. ISBN   0-262-03293-7 . Раздел 34.1: Полиномиальное время, стр. 971–979.
• Пападимитриу, Христос Х. (1994). Вычислительная сложность . Ридинг, Массачусетс: Аддисон – Уэсли. ISBN  978-0-201-53082-7 .
• Сипсер, Майкл (2006). Введение в теорию вычислений, 2-е издание . Курс Technology Inc. ISBN  978-0-534-95097-2 . Раздел 7.2: Класс P, стр. 256–263;.

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

• Зоопарк сложности : класс P
• Зоопарк сложности : Класс P/поли