П/поли

В теории вычислительной сложности P/poly — это класс сложности , представляющий проблемы, которые могут быть решены с помощью небольших схем. Точнее, это набор формальных языков, которые имеют семейства схем полиномиального размера. Его также можно эквивалентно определить в терминах машин Тьюринга с советами , дополнительной информацией, поставляемой машине Тьюринга вместе с ее входными данными, которая может зависеть от длины входных данных, но не от самих входных данных. В этой формулировке P/poly — это класс задач принятия решений , которые могут быть решены полиномиальной машиной Тьюринга со строками советов длины, полиномиальной по размеру входных данных. ^{[1] [2]} Эти два различных определения делают P/poly центральным для сложности схем и неоднородной сложности .

Например, популярный тест Миллера-Рабина на простоту можно сформулировать как алгоритм P/poly : «совет» — это список значений-кандидатов для проверки. Можно заранее вычислить список значений таким образом, что каждое составное n -битное число будет наверняка иметь свидетель a в списке. ^[3] Например, чтобы правильно определить простоту 32-битных чисел, достаточно проверить . ^{[4] [5]} Существование коротких списков свидетелей-кандидатов следует из того факта, что для каждого составного n три из четырех значений-кандидатов успешно определяют, что n является составным. Из этого следует простой аргумент подсчета, аналогичный аргументу в доказательстве, приведенном ниже, показывающий, что существует подходящий список значений-кандидатов для каждого размера входных данных, и, что более важно, что большинство достаточно длинных списков значений-кандидатов будут работать правильно, хотя поиск списка, который гарантированно будет работать, может быть затратным. ^[3]${\displaystyle O(n)}$${\displaystyle а\в \{2,7,61\}}$${\displaystyle {\mathsf {BPP}}\subset {\mathsf {P/поли}}}$

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

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

${\displaystyle {\mathsf {P/поли}}=\bigcup _{c\in \mathbb {N} }{\mathsf {SIZE}}(n^{c}),}$

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

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

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

${\displaystyle M(x,\alpha _{n})=1\Leftrightarrow x\in L}$

для каждого , где на входе машина M работает не более шагов. ^[6]${\displaystyle x\in \{0,1\}^{n}}$${\displaystyle (x,\alpha _{n})}$${\displaystyle O(T(n))}$

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

• Если NP ⊆ P/poly , то PH ( полиномиальная иерархия ) схлопывается до . Этот результат — теорема Карпа–Липтона ; кроме того, NP ⊆ P/poly подразумевает AM = MA ^[7]${\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 имеет протокол MA : Мерлин отправляет схему в качестве доказательства, а Артур может сам смоделировать протокол IP без какой-либо дополнительной помощи.

• Если P ^#P ⊆ P/poly , то P ^#P = MA . ^[8] Доказательство аналогично предыдущему, основано на интерактивном протоколе для перманента и #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 ^[9]
• Если EXP ^NP ⊆ P/poly , то (Бурман, Хомер) ^[10]${\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 = MA _EXP , поэтому EXPSPACE ⊆ P /poly , но это можно доказать ложным с помощью диагонализации.

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

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

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

Теорема Адлемана утверждает, что BPP ⊆ P/poly , где BPP — это множество задач, решаемых рандомизированными алгоритмами с двусторонней ошибкой за полиномиальное время. Более слабый результат был первоначально доказан Леонардом Адлеманом , а именно, что RP ⊆ P/poly ; ^[12] и этот результат был обобщен до BPP ⊆ P/poly Беннеттом и Гиллом. [ ^13] Варианты теоремы показывают, что 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{ is incorrect}}\}}$

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

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

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

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