Викиконспекты - Вклад участника [ru]

Теорема Карпа — Липтона

2012-06-03T14:51:03Z

95.55.114.72:

{{Лемма
|statement= Пусть <tex>\mathrm{SAT} \in \mathrm{P}/poly </tex>, тогда для любой формулы <tex>\phi</tex> с <tex>n</tex> переменными, существует такая последовательность схем полиномиального размера <tex>C_n^1...C_n^n</tex>, что <tex>C_n^i</tex> возвращает значение <tex>i</tex>-й переменной в наборе переменных, удовлетворяющих <tex>\phi</tex>, если <tex>\phi \in \mathrm{SAT}</tex>, или <tex>0</tex> если <tex>\phi \not \in \mathrm{SAT}</tex>
|proof=
Зададимся формулой <tex>\phi</tex>. Определим семейство схем <tex>C_n^1 ... C_n^n</tex> так: схема <tex>C_n^i</tex> будет принимать на вход формулу <tex>\phi</tex> и <tex>i-1</tex> бит <tex>b_1 ... b_{i-1}</tex>, и возвращать <tex>1</tex> тогда и только тогда, когда существует набор переменных, удовлетворяющий <tex>\phi</tex>, такой что <tex>x_1 = b_1 ... x_{i-1}=b_{i-1}</tex> и <tex>x_i=1</tex>. Так как задача определения выходного значения таких схем принадлежит <tex>\mathrm{NP}</tex>, то такие схемы существуют и имеют полиномиальный размер. Очевидно, что если формула <tex>\phi</tex> удовлетворима, то схема <tex>C_n^i</tex> вернет значение <tex>i</tex>-й переменной удовлетворяющего набора, в противном случае схема вернет <tex>0</tex>.
}}

{{Теорема
|author=Карп, Липтон
|statement=
Если <tex>\mathrm{NP} \subset \mathrm{P}/poly</tex>, то <tex>\Sigma_2 = \Pi_2</tex>.
|proof=
Рассмотрим язык <tex>L \in \mathrm{\Pi_2}</tex>, <tex>L = \{x \bigm| \forall y_1 . \exists y_2 \phi(x, y_1, y_2)\}</tex>. 
Рассмотрим семейство схем <tex>С_n^1...C_n^n</tex>из леммы. Используем выходы схем <tex>C_n^1...C_n^{i-1}</tex> как вход <tex>b_1...b_{i-1}</tex> схемы <tex>C_n^i</tex>, при этом заменяя те схемы <tex>C_n^i</tex>, которые возвращают значения переменных <tex>x</tex> и <tex>y_1</tex> на простые входы. Итого, получим схему <tex>C_n(\phi, x, y_1)</tex> и возвращающую такое значение <tex>y_2</tex>, что <tex> \phi(x, y_1, y_2) = 1</tex>, если <tex>\phi(x, y_1, y_2)</tex> удовлетворима для заданных <tex>x, y_1</tex>. Теперь определение языка можно переписать так: <tex>L = \{x \bigm| \forall y_1 \phi(x, y_1, C_n(\phi, x, y_1))\}</tex>. Покажем что <tex>(\forall y_1 \phi(x, y_1, C_n(\phi, x, y_1)))</tex> <tex>\Leftrightarrow</tex> <tex>(\exists G . \forall y_1 \phi(x, y_1, G(\phi, x, y_1)) )</tex>. Очевидно, что из первого следует второе, т.к. <tex>\exists G = C_n</tex>. Если первое ложно, то <tex>\exists y_1 = y_1^0 . \forall y_2 \phi(x, y_1^0, y_2) = 0</tex>, следовательно не существует такого <tex>G</tex>, что <tex>\forall y_1\phi(x, y_1, G(\phi, x, y_1)) )</tex>. 
Теперь определение исходного языка можно записать как <tex>L = \{x \bigm| \exists G . \forall y_1 \phi(x, y_1, G(\phi, x, y_1))\}</tex>, значит <tex>L \in \Sigma_2</tex>
}}

[[Категория: Теория сложности]]

Теорема Карпа — Липтона

2012-06-03T14:43:51Z

95.55.114.72:

{{Лемма
|statement= Пусть <tex>\mathrm{SAT} \in \mathrm{P}/poly </tex>, тогда для любой формулы <tex>\phi</tex> с <tex>n</tex> переменными, существует такая последовательность схем полиномиального размера <tex>C_n^1...C_n^n</tex>, что <tex>C_n^i</tex> возвращает значение <tex>i</tex>-й переменной в наборе переменных, удовлетворяющих <tex>\phi</tex>, если <tex>\phi \in \mathrm{SAT}</tex>, или <tex>0</tex> если <tex>\phi \not \in \mathrm{SAT}</tex>
|proof=
Зададимся формулой <tex>\phi</tex>. Определим семейство схем <tex>C_n^1 ... C_n^n</tex> так: схема <tex>C_n^i</tex> будет принимать на вход формулу <tex>\phi</tex> и <tex>i-1</tex> бит <tex>b_1 ... b_{i-1}</tex>, и возвращать <tex>1</tex> тогда и только тогда, когда существует набор переменных, удовлетворяющий <tex>\phi</tex>, такой что <tex>x_1 = b_1 ... x_{i-1}=b_{i-1}</tex> и <tex>x_i=1</tex>. Так как задача определения выходного значения таких схем принадлежит <tex>\mathrm{NP}</tex>, то такие схемы существуют и имеют полиномиальный размер. Очевидно, что если формула <tex>\phi</tex> удовлетворима, то схема <tex>C_n^i</tex> вернет значение <tex>i</tex>-й переменной удовлетворяющего набора, в противном случае схема вернет <tex>0</tex>.
}}

{{Теорема
|author=Карп, Липтон
|statement=
Если <tex>\mathrm{NP} \subset \mathrm{P}/poly</tex>, то <tex>\Sigma_2 = \Pi_2</tex>.
|proof=
Рассмотрим язык <tex>L \in \mathrm{\Pi_2}</tex>, <tex>L = \{x \bigm| \forall y_1 . \exists y_2 \phi(x, y_1, y_2)\}</tex>. 
Рассмотрим семейство схем <tex>С_n^1...C_n^n</tex>из леммы. Используем выходы схем <tex>C_n^1...C_n^{i-1}</tex> как вход <tex>b_1...b_{i-1}</tex> схемы <tex>C_n^i</tex>, при этом заменяя те схемы <tex>C_n^i</tex>, которые возвращают значения переменных <tex>x</tex> и <tex>y_1</tex> на простые входы. Итого, получим схему <tex>C_n(\phi, x, y_1)</tex> и возвращающую такое значение <tex>y_2</tex>, что <tex> \phi(x, y_1, y_2) = 1</tex>, если <tex>\phi(x, y_1, y_2)</tex> удовлетворима для заданных <tex>x, y_1</tex>. Теперь определение языка можно переписать так: <tex>L = \{x \bigm| \forall y_1 . \phi(x, y_1, C_n(\phi, x, y_1))\}</tex>. Покажем что <tex>(\forall y_1 \phi(x, y_1, C_n(\phi, x, y_1)))</tex> <tex>\Leftrightarrow</tex> <tex>(\exists G \forall y_1 \phi(x, y_1, G(\phi, x, y_1)) )</tex>. Очевидно, что из первого следует второе, т.к. <tex>\exists G = C_n</tex>. Если первое ложно, то <tex>\exists y_1 = y_1^0 . \forall y_2 \phi(x, y_1^0, y_2) = 0</tex>, следовательно не существует такого <tex>G</tex>, что <tex>\forall y_1\phi(x, y_1, G(\phi, x, y_1)) )</tex>. 
Теперь определение исходного языка можно записать как <tex>L = \{x \bigm| \exists G . \forall y_1 \phi(x, y_1, G(\phi, x, y_1))\}</tex>, значит <tex>L \in \Sigma_2</tex>
}}

[[Категория: Теория сложности]]