П / поли - P/poly

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

Например, популярный тест на простоту Миллера-Рабина может быть сформулирована в виде / поли P алгоритма: «Советы» список кандидатов а значения для тестирования. Можно предварительно вычислить список не более чем из n значений, так что каждое составное n- битное число обязательно будет иметь свидетеля a в списке. Например, чтобы правильно определить простоту 32-битных чисел, достаточно проверить a = 2, 7 и 61. Существование коротких списков кандидатов в свидетели следует из того факта, что для каждого составного n , 3/4 все возможные а значения свидетелей; простой подсчет аргумент похож на тот , в доказательстве того, что БППЫ в P / поли ниже , показывает , что существует соответствующий список через значение для каждого размера входных данных, хотя найти его может быть дорогими.

P / poly , в отличие от других классов с полиномиальным временем, таких как P или BPP , обычно не считается практическим классом для вычислений. Действительно, он содержит все неразрешимые унарные языки , ни один из которых не может быть решен на реальных компьютерах. С другой стороны, если длина ввода ограничена относительно небольшим числом, а строки рекомендаций короткие, их можно использовать для моделирования практических алгоритмов с отдельной дорогой фазой предварительной обработки и фазой быстрой обработки, как в приведенном выше примере.

Формальное определение

Класс сложности P / poly можно определить в терминах РАЗМЕРА следующим образом:

${\ displaystyle {\ mathsf {P / poly}} = \ cup _ {c \ in \ mathbb {N}} {\ mathsf {SIZE}} (n ^ {c}).}$

где - набор задач решения, которые могут быть решены с помощью семейств схем полиномиального размера. ${\ displaystyle {\ mathsf {SIZE}} (n ^ {c})}$

В качестве альтернативы, его можно определить с помощью машин Тьюринга, которые «следят за советом». Такая машина имеет для каждого п , в строке советы , которые ему разрешено использовать в вычислениях , когда вход имеет размер п . ${\ displaystyle {\ mathsf {P / poly}}}$ ${\ displaystyle \ alpha _ {n}}$

Позвольте быть функции. Класс языков, разрешимых с помощью T (n) машин Тьюринга с указанием времени T (n) с указанием совета, содержит каждый язык L такой, что существует последовательность строк с и TM M, удовлетворяющая ${\ Displaystyle Т, а: \ mathbb {N} \ rightarrow \ mathbb {N}}$${\ Displaystyle а (п)}$${\ Displaystyle {\ mathsf {DTIME}} (Т (п)) / а (п)}$${\ displaystyle \ {\ alpha _ {n} \} _ {n \ in \ mathbb {N}}}$${\ Displaystyle \ альфа _ {п} \ в \ {0,1 \} ^ {а (п)}}$

${\ Displaystyle М (х, \ альфа _ {п}) = 1 \ Leftrightarrow х \ в L}$

для каждого , где на входе машина M работает не более чем за шаги. ${\ Displaystyle х \ в \ {0,1 \} ^ {п}}$${\ Displaystyle (х, \ альфа _ {п})}$${\ Displaystyle О (Т (п))}$

Важность P / poly

P / poly - важный класс по нескольким причинам. Для теоретической информатики есть несколько важных свойств, которые зависят от P / poly :

• Если NP ⊆ P / poly, то PH ( иерархия полиномов ) схлопывается до . Этот результат представляет собой теорему Карпа – Липтона ; кроме того, NP ⊆ P / poly влечет AM = MA${\ Displaystyle \ Sigma _ {2} ^ {\ mathsf {P}}}$
• Если PSPACE ⊆ P / poly, то даже PSPACE = MA .${\ displaystyle {\ mathsf {PSPACE}} = \ Sigma _ {2} ^ {\ mathsf {P}} \ cap \ Pi _ {2} ^ {\ mathsf {P}}}$

Доказательство: рассмотрим язык L из PSPACE . Известно, что существует интерактивная система доказательства для L , в которой действия доказывающего могут выполняться машиной PSPACE . По предположению, доказывающий может быть заменен схемой полиномиального размера. Следовательно, у L есть протокол МА : Мерлин отправляет схему в качестве доказательства, а Артур может сам смоделировать протокол IP без какой-либо дополнительной помощи.

• Если P ^#P ⊆ P / poly, то P ^#P = MA . Доказательство аналогично приведенному выше, основанному на интерактивном протоколе для перманентности и # P-полноты перманентности .
• Если EXPTIME ⊆ P / poly, то (теорема Мейера) даже EXPTIME = MA .${\ displaystyle {\ mathsf {EXPTIME}} = \ Sigma _ {2} ^ {\ mathsf {P}} \ cap \ Pi _ {2} ^ {\ mathsf {P}}}$
• Если NEXPTIME ⊆ P / poly, то NEXPTIME = EXPTIME , даже NEXPTIME = MA . И наоборот, NEXPTIME = MA влечет NEXPTIME ⊆ P / poly
• Если EXP ^NP ⊆ P / poly, то (Бурман, Гомер)${\ displaystyle {\ mathsf {EXP ^ {NP}}} = \ Sigma _ {2} ^ {\ mathsf {P}} \ cap \ Pi _ {2} ^ {\ mathsf {P}}}$
• Известно, что MA _EXP , экспоненциальная версия MA , не содержится в P / poly .

Доказательство: если MA _EXP ⊆ P / poly, то PSPACE = MA (см. Выше). По обивка , EXPSPACE = МА _EXP , поэтому EXPSPACE ⊆ P / поли , но это может быть доказана ложная диагонализацией.

Одна из наиболее интересных причин важности P / poly заключается в том, что если NP не является подмножеством P / poly , то P ≠ NP . Это наблюдение было центром многих попыток доказать P ≠ NP . Известно , что для случайного оракула А , НП не является подмножество P ^A / поли с вероятностью 1.

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

Хотя не все языки в P / poly являются разреженными языками , существует редукция по Тьюрингу за полиномиальное время от любого языка в P / poly до разреженного языка.

Вероятностный полином с ограниченной погрешностью содержится в P / poly

Теорема Адлемана утверждает, что BPP ⊆ P / poly , где BPP - это набор задач, решаемых с помощью рандомизированных алгоритмов с двусторонней ошибкой за полиномиальное время. Более слабый результат был первоначально доказан Леонардом Адлеманом , а именно, что RP ⊆ P / poly ; и этот результат был обобщен на БППЫ ⊆ P / поли по Беннета и Гилла. Варианты теоремы показывают, что BPL содержится в L / poly, а AM содержится в NP / poly .

Доказательство

Пусть L - язык в BPP , и пусть M ( x , r ) - алгоритм с полиномиальным временем, который решает L с ошибкой ≤ 1/3 (где x - входная строка, а r - набор случайных битов).

Создайте новую машину M ' ( x , R ), которая запускает M 48 n раз и принимает большинство результатов (где n - длина ввода, а R - последовательность из 48 n независимо случайных r s). Таким образом, M ' также является полиномиальным временем и имеет вероятность ошибки ≤ 1 / e ⁿ по границе Чернова (см. BPP ). Если мы можем исправить R, то получим детерминированный алгоритм.

Если определяется как , мы имеем: ${\ displaystyle {\ mbox {Bad}} (x)}$${\ displaystyle \ {R: M {'} (x, R) {\ text {неверно}} \}}$

${\ displaystyle \ forall x \, {\ mbox {Prob}} _ {R} [R \ in {\ mbox {Bad}} (x)] \ leq {\ frac {1} {e ^ {n}}} .}$

Размер ввода равен n , поэтому существует 2 ⁿ возможных входов. Таким образом, согласно оценке объединения , вероятность того, что случайное R является плохим хотя бы для одного входа x, равна

${\ displaystyle {\ mbox {Prob}} _ {R} [\ существует x \, R \ in {\ mbox {Bad}} (x)] \ leq {\ frac {2 ^ {n}} {e ^ { n}}} <1.}$

Другими словами, вероятность того, что R является плохим для некоторого x , меньше 1, поэтому должно быть R, которое является хорошим для всех x . Возьмите такое R в качестве строки совета в нашем алгоритме P / poly .

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