Теорема Сипсера–Лаутемана

В теории сложности вычислений теорема Сипсера –Лаутемана или теорема Сипсера–Гача–Лаутемана утверждает, что вероятностное полиномиальное время с ограниченной ошибкой (BPP) содержится в иерархии полиномиального времени , а точнее, _Σ2 ∩ _Π2 .

В 1983 году Майкл Сипсер показал, что BPP содержится в иерархии полиномиального времени . ^[1] Петер Гач показал, что BPP на самом деле содержится в Σ ₂ ∩ Π ₂ . Клеменс Лаутеманн внес свой вклад, предоставив простое доказательство членства BPP в Σ ₂ ∩ Π ₂ , также в 1983 году. ^[2] Предполагается, что на самом деле BPP = P , что является гораздо более сильным утверждением, чем теорема Сипсера–Лаутеманна.

Здесь мы представляем доказательство Лаутеманна. ^[2] Без потери общности можно выбрать машину M ∈ BPP с ошибкой ≤ 2 ^{−| x | . (Все проблемы BPP можно усилить, чтобы уменьшить вероятность ошибки экспоненциально.) Основная идея доказательства состоит в определении предложения Σ} ₂ , которое эквивалентно утверждению, что x находится в языке L , определяемом M , с помощью набора преобразований случайных входных величин.

Поскольку вывод M зависит от случайного ввода, а также от ввода x , полезно определить, какие случайные строки производят правильный вывод, как A ( x ) = { r | M ( x , r ) принимает}. Ключ к доказательству заключается в том, чтобы отметить, что когда x ∈ L , A ( x ) очень велико, а когда x ∉ L , A ( x ) очень мало. Используя побитовую четность , ⊕, набор преобразований можно определить как A ( x ) ⊕ t = { r ⊕ t | r ∈ A ( x )}. Первая основная лемма доказательства показывает, что объединение небольшого конечного числа этих преобразований будет содержать все пространство случайных входных строк. Используя этот факт, можно сгенерировать предложение Σ ₂ и предложение Π ₂ , которые являются истинными тогда и только тогда, когда x ∈ L (см. заключение).

Общая идея леммы один — доказать, что если A ( x ) покрывает большую часть случайного пространства , то существует небольшой набор переводов, который покроет все случайное пространство. На более математическом языке:${\displaystyle R=\{1,0\}^{|r|}}$

Если , то , где такое, что${\displaystyle {\frac {|A(x)|}{|R|}}\geq 1-{\frac {1}{2^{|x|}}}}$ ${\displaystyle \exists t_{1},t_{2},\ldots ,t_{|r|}}$ ${\displaystyle t_{i}\in \{1,0\}^{|r|}}$ ${\displaystyle \bigcup _{i}A(x)\oplus t_{i}=R.}$

Доказательство. Случайным образом выберем t ₁ , t ₂ , ..., t _{| r |} . Пусть (объединение всех преобразований A ( x )).${\displaystyle S=\bigcup _{i}A(x)\oplus t_{i}}$

Итак, для всех r из R ,

${\displaystyle \Pr[r\notin S]=\Pr[r\notin A(x)\oplus t_{1}]\cdot \Pr[r\notin A(x)\oplus t_{2}]\cdots \Pr[r\notin A(x)\oplus t_{|r|}]\leq {\frac {1}{2^{|x|\cdot |r|}}}.}$

Вероятность того, что в R будет существовать хотя бы один элемент, которого нет в S, равна

${\displaystyle \Pr {\Bigl [}\bigvee _{i}(r_{i}\notin S){\Bigr ]}\leq \sum _{i}{\frac {1}{2^{|x|\cdot |r|}}}={\frac {2^{|r|}}{2^{|x|\cdot |r|}}}<1.}$

Поэтому

${\displaystyle \Pr[S=R]\geq 1-{\frac {2^{|r|}}{2^{|x|\cdot |r|}}}>0.}$

Таким образом, для каждого существует выборка, такая что${\displaystyle t_{1},t_{2},\ldots ,t_{|r|}}$

${\displaystyle \bigcup _{i}A(x)\oplus t_{i}=R.}$

Предыдущая лемма показывает, что A ( x ) может покрыть каждую возможную точку в пространстве, используя небольшой набор переносов. В дополнение к этому, для x ∉ L только небольшая часть пространства покрывается . Мы имеем:${\displaystyle S=\bigcup _{i}A(x)\oplus t_{i}}$

${\displaystyle {\frac {|S|}{|R|}}\leq |r|\cdot {\frac {|A(x)|}{|R|}}\leq |r|\cdot 2^{-|x|}<1}$

поскольку является полиномом по .${\displaystyle |г|}$${\displaystyle |x|}$

Леммы показывают, что принадлежность языка к BPP может быть выражена как выражение Σ2 _{следующим} образом.

${\displaystyle x\in L\если и только если \существует t_{1},t_{2},\dots ,t_{|r|}\,\forall r\in R\bigvee _{1\leq i\leq |r|}(M(x,r\oplus t_{i}){\text{ принимает}}).}$

То есть x находится в языке L тогда и только тогда, когда существуют двоичные векторы, где для всех случайных битовых векторов r TM M принимает по крайней мере один случайный вектор ⊕ t _i .${\displaystyle |г|}$

Вышеприведенное выражение принадлежит Σ ₂ в том смысле, что оно сначала экзистенциально, а затем универсально квантифицировано. Следовательно, BPP ⊆ Σ ₂ . Поскольку BPP замкнуто относительно дополнения , это доказывает, что BPP ⊆ Σ ₂ ∩ Π ₂ .

Теорему можно усилить до (см. MA , S${\displaystyle {\mathsf {BPP}}\subseteq {\mathsf {MA}}\subseteq {\mathsf {S}}_{2}^{P}\subseteq \Sigma _{2}\cap \Pi _{2}}$^П
₂). ^{[3] [4]}