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

P (complexity)

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

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

Определение

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

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

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

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

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

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

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

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

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

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

Известно также, что 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, то ее можно решить за детерминированное полиномиальное время при условии, что строка совета дается, что зависит только от длины ввода. Однако, в отличие от NP, машине полиномиального времени не требуется обнаруживать мошеннические строки с советами; это не верификатор. P / poly - большой класс, содержащий почти все практические задачи, включая все BPP. Если он содержит NP, то полиномиальная иерархия сворачивается на второй уровень. С другой стороны, он также содержит некоторые непрактичные проблемы, в том числе некоторые неразрешимые проблемы например, унарная версия любой неразрешимой проблемы.

В 1999 году Джин-И Цай и Д. Сивакумар, опираясь на работу Мицунори Огихара, показал, что если существует скудный язык то есть P-полное, то L = P.[5]

Свойства

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

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

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

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

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

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

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

История

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

Заметки

  1. ^ Маниндра Агравал, Нирадж Каял, Нитин Саксена "PRIMES находится в P", Анналы математики 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 г.. Получено 2020-10-14.
  5. ^ Джин-И Цай и Д. Сивакумар. Редкие жесткие множества для 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. ^ Варди, Моше Ю. (1982). «Сложность языков реляционных запросов». STOC '82: Материалы четырнадцатого ежегодного симпозиума ACM по теории вычислений. С. 137–146. Дои:10.1145/800070.802186.
  9. ^ Иммерман, Нил (1982). «Реляционные запросы, вычислимые за полиномиальное время». STOC '82: Материалы четырнадцатого ежегодного симпозиума ACM по теории вычислений. С. 147–152. Дои:10.1145/800070.802187. Исправленная версия в Информация и контроль, 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. ^ Козен, Декстер К. (2006). Теория вычислений. Springer. п. 4. ISBN 978-1-84628-297-3.
  12. ^ Поклингтон, Х.С. (1910–1912). «Определение показателя степени, которому принадлежит число, практическое решение некоторых сравнений и закон квадратичной взаимности». Proc. Camb. Фил. Soc. 16: 1–5.
  13. ^ Гаучи, Вальтер (1994). Математика вычислений, 1943–1993: полвека вычислительной математики: Симпозиум по 50-летию математики вычислений, 9–13 августа 1993 г., Ванкувер, Британская Колумбия. Провиденс, Род-Айленд: Американское математическое общество. С. 503–504. ISBN 978-0-8218-0291-5.

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

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