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

Класс задач, решаемых за полиномиальное время

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

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

Определение

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

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

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

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

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

Известные проблемы в P

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

Несколько естественных проблем являются полными для P, включая st -связность (или достижимость ) на чередующихся графах. ^[2] Статья о P-полных проблемах перечисляет другие соответствующие проблемы в P.

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

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

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

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

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

${\displaystyle {\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. ^[5]

P в отношении вероятностных классов сложности ( ZPP , RP , co-RP, BPP , BQP , PP ), все в пределах PSPACE . Неизвестно, являются ли какие-либо из этих ограничений строгими.

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

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

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

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

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

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

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

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

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

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

История

Козен ^[12] утверждает, что Кобэму и Эдмондсу «обычно приписывают изобретение понятия полиномиального времени», хотя Рабин также изобрел это понятие независимо и примерно в то же время (статья Рабина ^[13] была в трудах конференции 1966 года 1967 года, в то время как статья Кобэма ^[14] была в трудах конференции 1964 года 1965 года, а статья Эдмондса ^[15] была опубликована в журнале в 1965 году, хотя Рабин не упоминает ни одну из них и, по-видимому, не знал о них). Кобэм изобрел класс как надежный способ характеристики эффективных алгоритмов, что привело к тезису Кобэма . Однако Х. К. Поклингтон в своей статье 1910 года ^{[16] [17]} проанализировал два алгоритма решения квадратных сравнений и заметил, что один из них требует времени, «пропорционального степени логарифма модуля», и сравнил его с алгоритмом, требующим времени, пропорционального «самому модулю или его квадратному корню», тем самым явно проводя различие между алгоритмом, который работает за полиномиальное время, и алгоритмом, который работает за (умеренно) экспоненциальное время.

Примечания

1. Маниндра Агравал, Нирадж Каял, Нитин Саксена, «ПРАЙМЫ находятся в P», Annals of Mathematics 160 (2004), вып. 2, стр. 781–793.
2. Иммерман, Нил (1999). Описательная сложность . Нью-Йорк: Springer-Verlag. ISBN 978-0-387-98600-5.
3. Джонсонбо, Ричард Ф .; Шефер, Маркус (2004). Алгоритмы . Pearson Education. стр. 458. ISBN 0-02-360692-4.
4. "теория сложности - Почему co-P = P". Stack Overflow . Архивировано из оригинала 14 октября 2020 г. Получено 2020-10-14 .
5. Cai, Jin-Yi ; Sivakumar, D. (апрель 1999 г.). «Разреженные жесткие множества для P: разрешение гипотезы Хартманиса». Журнал компьютерных и системных наук . 58 (2): 280–296. doi : 10.1006/jcss.1998.1615 .
6. Хопкрофт, Джон Э.; Раджив Мотвани; Джеффри Д. Ульман (2001). Введение в теорию автоматов, языки и вычисления (2-е изд.). Бостон: Addison-Wesley. С. 425–426. ISBN 978-0201441246.
7. Иммерман, Нил (1999). Описательная сложность . Нью-Йорк: Springer-Verlag. С. 66. ISBN 978-0-387-98600-5.
8. Варди, Моше Й. (1982). «Сложность реляционных языков запросов». STOC '82: Труды четырнадцатого ежегодного симпозиума ACM по теории вычислений . стр. 137–146. doi :10.1145/800070.802186.
9. Иммерман, Нил (1982). «Реляционные запросы, вычислимые за полиномиальное время». STOC '82: Труды четырнадцатого ежегодного симпозиума ACM по теории вычислений . С. 147–152. doi :10.1145/800070.802187. Пересмотренная версия в Information and Control , 68 (1986), 86–104.
10. Лора Каллмейер (2010). Анализ за пределами контекстно-свободных грамматик . Springer Science & Business Media. стр. 5 и 37. ISBN 978-3-642-14846-0.Ссылка на http://mjn.host.cs.st-andrews.ac.uk/publications/2001d.pdf для доказательства
11. Вегенер, Инго (2005). Теория сложности . Springer-Verlag. стр. 35. doi :10.1007/3-540-27477-4. ISBN 978-3-540-21045-0.
12. Козен, Декстер С. (2006). Теория вычислений . Спрингер. п. 4. ISBN 978-1-84628-297-3.
13. Рабин, Майкл О. (1967). «Математическая теория автоматов». Математические аспекты информатики. Труды Симпоз. Прикладная математика, т. XIX . Американское мат. общество. стр. 153–175.
14. Кобэм, Алан (1965). «Внутренняя вычислительная сложность функций». Логика, методология и философские науки (Proc. 1964 Internat. Congr.) . С. 24–30.
15. Эдмондс, Дж. (1965). «Пути, деревья и цветы». Canadian J. Math . 17 : 449–467. doi :10.4153/CJM-1965-045-4.
16. Поклингтон, ХК (1910–1912). «Определение показателя степени, к которому принадлежит число, практическое решение некоторых сравнений и закон квадратичной взаимности». Proc. Camb. Phil. Soc . 16 : 1–5.
17. Гаучи, Уолтер (1994). Математика вычислений, 1943–1993: полвека вычислительной математики: Симпозиум по 50-летию математики вычислений, 9–13 августа 1993 г., Ванкувер, Британская Колумбия . Провиденс, Род-Айленд: Американское математическое общество. стр. 503–504. ISBN 978-0-8218-0291-5.

Ссылки

• Эдмондс, Дж. (1965). «Дорожки, деревья и цветы». Canadian J. Math . 17 : 449–467. doi :10.4153/CJM-1965-045-4.
• Кобэм, Алан (1965). «Внутренняя вычислительная сложность функций». Proc. Логика, методология и философия науки II 1964. Северная Голландия.
• Рабин, Майкл О. (1967). «Математическая теория автоматов». Математические аспекты информатики. Труды 1966 Sympos. Appl. Math., т. XIX . Amer. Math. Soc. стр. 153–175.
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest и Clifford Stein . Введение в алгоритмы , второе издание. MIT Press и McGraw–Hill, 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/поли