Теорема Сипсера – Лаутеманна. - Sipser–Lautemann theorem

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

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

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

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

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

Лемма 1.

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

Если ${ displaystyle { frac {| A (x) |} {| R |}} geq 1 - { frac {1} {2 ^ {| x |}}}}$, тогда ${ Displaystyle существует t_ {1}, t_ {2}, ldots, t_ {| r |}}$, куда ${ displaystyle t_ {i} in {1,0 } ^ {| r |}}$ такой, что ${ Displaystyle bigcup _ {я} А (х) oplus t_ {я} = Р.}$

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

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

${ Displaystyle Pr [р 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 |}}}.}$

Вероятность существования хотя бы одного элемента в р не в 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 _ {я} А (х) oplus t_ {я} = Р.}$

Лемма 2

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

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

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

Вывод

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

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

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

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

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

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

Рекомендации