Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В теории сложности вычислений , Р , также известный как 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. [1] Связанный класс функциональных задач - FP .

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

Отношения с другими классами [ править ]

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

Также известно, что 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. [5]

Свойства [ править ]

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

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

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

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

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

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

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

История [ править ]

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

Примечания [ править ]

  1. ^ Маниндра Агравал, Neeraj Каяль, Нитин Саксена, " PRIMES в Р ", Анналы математики 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" . Переполнение стека . Архивировано 14 октября 2020 года . Проверено 14 октября 2020 .
  5. ↑ Jin-Yi Cai и D. Sivakumar. Редкие жесткие множества для P: разрешение гипотезы Хартманиса. Журнал компьютерных и системных наук , том 58, выпуск 2, стр.280–296. 1999. ISSN 0022-0000 . В Citeseer 
  6. ^ Хопкрофт, Джон Э .; Раджив Мотвани; Джеффри Д. Ульман (2001). Введение в теорию автоматов, языки и вычисления (2-е изд.). Бостон: Эддисон-Уэсли. С. 425–426. ISBN 978-0201441246.
  7. ^ Иммерман, Нил (1999). Описательная сложность . Нью-Йорк: Springer-Verlag. п. 66. ISBN 978-0-387-98600-5.
  8. Перейти ↑ Vardi, Moshe Y. (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. Перейти ↑ Kozen, Dexter C. (2006). Теория вычислений . Springer. п. 4. ISBN 978-1-84628-297-3.
  12. ^ Pocklington, HC (1910-1912). «Определение показателя степени, которому принадлежит число, практическое решение некоторых сравнений и закон квадратичной взаимности». Proc. Camb. Фил. Soc . 16 : 1–5.
  13. ^ Gautschi, Вальтер (1994). Математика вычислений, 1943–1993: полвека вычислительной математики: Симпозиум по 50-летию математики вычислений, 9–13 августа 1993 г., Ванкувер, Британская Колумбия . Провиденс, Род-Айленд: Американское математическое общество. С. 503–504. ISBN 978-0-8218-0291-5.

Ссылки [ править ]

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

Внешние ссылки [ править ]

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