П/поли

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

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

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

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

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

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

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

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

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

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

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

Важность P/poly

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

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

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

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

Доказательство: если MA _EXP ⊆ P/poly , то PSPACE = MA (см. выше). При заполнении EXPSPACE EXPSPACE = MA _EXP , следовательно, . ⊆ P/poly, но это можно доказать с помощью диагонализации

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

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

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

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

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

Если ${\mbox{Bad}}(x)$ определяется как $\{R:M{'}(x,R){\text{ is incorrect}}\}$, у нас есть:

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

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

${\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 -алгоритме.