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

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

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

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

Здесь мы приводим доказательство Лаутмана. Без ограничения общности, машина M ∈ BPP с ошибкой ≤ 2 ^{−| х |} можно выбрать. (Все проблемы 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 | А г € ( Икс ) }. Первая основная лемма доказательства показывает, что объединение небольшого конечного числа этих преобразований будет содержать все пространство случайных входных строк. предложение Σ ₂ и предложение Π ₂ Используя этот факт, можно сгенерировать , которые будут истинными тогда и только тогда, когда x ∈ L (см. вывод).

Лемма 1

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

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

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

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

$\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, равна

$\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.$

Поэтому

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

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

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

Лемма 2

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

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

потому что $|r|$ полиномиален по $|x|$.

Заключение

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

$x\in L\iff \exists t_{1},t_{2},\dots ,t_{|r|}\,\forall r\in R\bigvee _{1\leq i\leq |r|}(M(x,r\oplus t_{i}){\text{ accepts}}).$

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

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

Более сильная версия

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