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

В теории сложности вычислений , 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. ^[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] хотя это убеждение (т. ${\mathsf {P}}\subsetneq {\mathsf {NP}}$ гипотеза) остается недоказанной . Другая открытая проблема заключается в том, = NP = co-NP; поскольку P = co-P, ^[4] отрицательный ответ будет означать ${\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. ^[5]

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]утверждает, что Кобэму и Эдмондсу «обычно приписывают изобретение понятия полиномиального времени». Кобэм изобрел этот класс как надежный способ характеристики эффективных алгоритмов, что привело к диссертации Кобэма . Однако Г.С. Поклингтон в статье 1910 г. ^[13]^[14] проанализировал два алгоритма решения квадратичных сравнений и заметил, что один из них требует времени, «пропорционального степени логарифма модуля», и противопоставляет его алгоритму, который требует времени, пропорционального «самому модулю или его квадратному корню», тем самым явно рисуя различие между алгоритмом, который работал за полиномиальное время, и алгоритмом, который этого не делал.

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

^ Маниндра Агравал, Нирадж Каял, Нитин Саксена, « ПРАЙМСЫ находятся в P », Annals of Mathematics 160 (2004), вып. 2, с. 781–793.
^ Иммерман, Нил (1999). Описательная сложность . Нью-Йорк: Springer-Verlag. ISBN 978-0-387-98600-5 .
^ Джонсонбо, Ричард Ф .; Шефер, Маркус (2004). Алгоритмы . Пирсон Образование. п. 458. ИСБН 0-02-360692-4 .
^ "Теория сложности - Почему со-Р = Р" . Переполнение стека . Архивировано из оригинала 14 октября 2020 года . Проверено 14 октября 2020 г.
^ Цай, Джин-И ; Сивакумар, Д. (апрель 1999 г.). «Разреженные жесткие множества для P: разрешение гипотезы Хартманиса» . Журнал компьютерных и системных наук . 58 (2): 280–296. дои : 10.1006/jcss.1998.1615 .
^ Хопкрофт, Джон Э.; Раджив Мотвани; Джеффри Д. Уллман (2001). Введение в теорию автоматов, языки и вычисления (2-е изд.). Бостон: Аддисон-Уэсли. стр. 425–426. ISBN 978-0201441246 .
^ Иммерман, Нил (1999). Описательная сложность . Нью-Йорк: Springer-Verlag. п. 66. ИСБН 978-0-387-98600-5 .
^ Варди, Моше Ю. (1982). «Сложность реляционных языков запросов». STOC '82: Материалы четырнадцатого ежегодного симпозиума ACM по теории вычислений . стр. 137–146. дои : 10.1145/800070.802186 .
^ Иммерман, Нил (1982). «Реляционные запросы, вычисляемые за полиномиальное время». STOC '82: Материалы четырнадцатого ежегодного симпозиума ACM по теории вычислений . стр. 147–152. дои : 10.1145/800070.802187 . Пересмотренная версия в Information and Control , 68 (1986), 86–104.
^ Лаура Каллмейер (2010). Синтаксический анализ за пределами контекстно-свободных грамматик . Springer Science & Business Media. стр. 5 и 37. ISBN 978-3-642-14846-0 . цитируя http://mjn.host.cs.st-andrews.ac.uk/publications/2001d.pdf для доказательства
^ Вегенер, Инго (2005). Теория сложности . Спрингер-Верлаг. п. 35. дои : 10.1007/3-540-27477-4 . ISBN 978-3-540-21045-0 .
^ Козен, Декстер К. (2006). Теория вычислений . Спрингер. п. 4. ISBN 978-1-84628-297-3 .
^ Поклингтон, ХК (1910–1912). «Определение показателя степени, которому принадлежит число, практическое решение некоторых сравнений и закон квадратичной взаимности». Учеб. Кэмб. Фил. Соц . 16 : 1–5.
^ Гаучи, Уолтер (1994). Математика вычислений, 1943–1993: полвека вычислительной математики: Симпозиум, посвященный 50-летию математики вычислений, 9–13 августа 1993 г., Ванкувер, Британская Колумбия . Провиденс, Род-Айленд: Американское математическое общество. стр. 503–504. ISBN 978-0-8218-0291-5 .

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

Кобэм, Алан (1965). «Внутренняя вычислительная сложность функций». Учеб. Логика, методология и философия науки II . Северная Голландия.
Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стейн . Введение в алгоритмы , второе издание. 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;.

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

[1] Маниндра Агравал, Нирадж Каял, Нитин Саксена, « ПРАЙМСЫ находятся в P », Annals of Mathematics 160 (2004), вып. 2, с. 781–793.

[Immerman_Reachability-2] Иммерман, Нил (1999). Описательная сложность . Нью-Йорк: Springer-Verlag. ISBN 978-0-387-98600-5 .

[3] Джонсонбо, Ричард Ф .; Шефер, Маркус (2004). Алгоритмы . Пирсон Образование. п. 458. ИСБН 0-02-360692-4 .

[4] "Теория сложности - Почему со-Р = Р" . Переполнение стека . Архивировано из оригинала 14 октября 2020 года . Проверено 14 октября 2020 г.

[5] Цай, Джин-И ; Сивакумар, Д. (апрель 1999 г.). «Разреженные жесткие множества для P: разрешение гипотезы Хартманиса» . Журнал компьютерных и системных наук . 58 (2): 280–296. дои : 10.1006/jcss.1998.1615 .

[6] Хопкрофт, Джон Э.; Раджив Мотвани; Джеффри Д. Уллман (2001). Введение в теорию автоматов, языки и вычисления (2-е изд.). Бостон: Аддисон-Уэсли. стр. 425–426. ISBN 978-0201441246 .

[7] Иммерман, Нил (1999). Описательная сложность . Нью-Йорк: Springer-Verlag. п. 66. ИСБН 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 . Пересмотренная версия в Information and Control , 68 (1986), 86–104.

[Kallmeyer2010-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 для доказательства

[Wegener2005-11] Вегенер, Инго (2005). Теория сложности . Спрингер-Верлаг. п. 35. дои : 10.1007/3-540-27477-4 . ISBN 978-3-540-21045-0 .

[12] Козен, Декстер К. (2006). Теория вычислений . Спрингер. п. 4. ISBN 978-1-84628-297-3 .

[13] Поклингтон, ХК (1910–1912). «Определение показателя степени, которому принадлежит число, практическое решение некоторых сравнений и закон квадратичной взаимности». Учеб. Кэмб. Фил. Соц . 16 : 1–5.

[14] Гаучи, Уолтер (1994). Математика вычислений, 1943–1993: полвека вычислительной математики: Симпозиум, посвященный 50-летию математики вычислений, 9–13 августа 1993 г., Ванкувер, Британская Колумбия . Провиденс, Род-Айленд: Американское математическое общество. стр. 503–504. ISBN 978-0-8218-0291-5 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

v т Это Классы сложности
Считается возможным	ДЛОГТАЙМ переменного тока ⁰ АСС ⁰ ТК ⁰ л СЛ РЛ Флорида Нидерланды NL-полный Северная Каролина СК СС п P-полный ЗПП РП БПП Министерство национальной обороны АПХ ФП
Подозрение на невозможность	ВВЕРХ НАПРИМЕР NP-полный NP-жесткий со-НП со-NP-полный ТФНП ФНП ЯВЛЯЮСЬ КМА PH ⊕P ПП #П #P-полное ИП PSPACE PSPACE-полный
Считается невозможным	ВРЕМЯ ЭКСПРЕСС СЛЕДУЮЩЕЕ ВРЕМЯ EXPSPACE 2-ВРЕМЯ ЭКСПЛУАТАЦИИ ЭЛЕМЕНТАРНЫЙ пиар р РЭ ВСЕ
Иерархии классов	Полиномиальная иерархия Экспоненциальная иерархия Иерарх Гжегорчик Арифметическая иерархия Булева иерархия
Семьи классов	DTIME NTIME ДСПЕЙС НСПАСЕ Вероятностно проверяемое доказательство Интерактивная система доказательств
Список классов сложности