210
правок
Изменения
м
Нет описания правки
{{Определение
|definition=
<tex>\mathrm{\#SAT}=\{\langle \varphi, k \rangle \mid \varphi</tex> {{---}} [[Определение_булевой_функции | булева формула]], которая имеет ровно <tex>k</tex> удовлетворяющих наборов <tex>\}</tex>.
}}
{{Лемма
|about=1
|statement=Пусть <tex> \varphi </tex> булева формула, а <tex> A_\varphi </tex> {{---}} её [[Арифметизация булевых формул с кванторами|арифметизация]]. Тогда <tex>\sum\limits_{x_1 = 0}^1 \ldots \sum\limits_{x_m = 0}^1 A_\varphi(x_1, \ldots, x_m)=k \Leftrightarrow \langle \varphi,k\rangle \in \mathrm{\#SAT}</tex>.
|proof=Следует из [[Арифметизация булевых формул с кванторами | леммы (1)]].
}}
Для доказательства леммы построим программы <tex>V</tex> (<tex> \mathit{Verifier}</tex>) и <tex>P</tex> (<tex>\mathit{Prover}</tex>) из [[Интерактивные протоколы. Класс IP. Класс AM#Класс IP|определения]] класса <tex>\mathrm{IP}</tex>.
Сперва [[Арифметизация булевых формул с кванторами|арифметизуем]] формулу <tex>\varphi</tex>. Пусть полученный полином <tex>AA_\varphi(x_1, x_2, \ldots, x_m)</tex> имеет степень <tex>d</tex>.
По лемме (1) вместо условия <tex>\langle \varphi, k \rangle \in \mathrm{\#SAT}</tex>, можно проверять условие <tex>\sum\limits_{x_1 = 0}^1 \ldots \sum\limits_{x_m = 0}^1 AA_\varphi(x_1, \ldots, x_m)=k</tex>.
Приступим к описанию [[Интерактивные протоколы. Класс IP. Класс AM|интерактивного протокола]].
Далее будем проводить все вычисления модулю <tex>p</tex>, то есть над конечным полем <tex> \mathbb{F}_{p} </tex>, что не позволяет числам становиться слишком большими и упрощает анализ.
Попросим <tex>P</tex> прислать <tex>V</tex> формулу <tex>A_0(x_1)= \sum\limits_{x_2 = 0}^{1}\ldots\sum\limits_{x_m = 0}^{1} AA_\varphi(x_1, x_2, \ldots, x_m)</tex>.
Заметим, что размер формулы <tex>A_0(x_1)</tex> будет полином от длины входа <tex>V</tex>, так как <tex>A_0(x_1)</tex> — полином степени не выше, чем <tex>d</tex>, от одной переменной, а значит его можно представить в виде <tex>A_0(x) = \sum\limits_{i = 0}^{d} C_i \cdot x ^ i</tex>.
Пусть <tex>r_i = \mathrm{random} \lbrace0, \ldots, p-1 \rbrace</tex>. Отправим <tex>r_i</tex> программе <tex>P</tex>.
Попросим <tex>P</tex> прислать <tex>V</tex> формулу <tex>A_i(x_{i+1}) = \sum\limits_{x_{i+2} = 0}^{1}\ldots\sum\limits_{x_m = 0}^{1} AA_\varphi(r_1,\ldots, r_i, x_{i+1}, \ldots, x_m)</tex>.
Проверим следующее утверждение: <tex>A_i(0) + A_i(1) = A_{i-1}(r_i)</tex> (*).
Пусть <tex>r_m = \mathrm{random} \lbrace0, \ldots, p-1 \rbrace</tex>. Отправим <tex>r_m</tex> программе <tex>P</tex>.
Попросим программу <tex>P</tex> прислать <tex>V</tex> значение <tex>A_m()= AA_\varphi(r_1, r_2, \ldots, r_m)</tex>.
Проверим следующее утверждение: <tex>A_m() = A_{m-1}(r_m)</tex> (*).
А также сами подставим <tex>r_1, r_2, \ldots, r_m</tex> в <tex>AA_\varphi(x_1, x_2, \ldots, x_m)</tex> и проверим правильность присланного значения <tex>A_m()</tex>.
Возвращаем '''true'''.
#Пусть количество наборов, удовлетворяющих <tex>\varphi</tex>, не равно <tex>k</tex>. Для того, чтобы <tex>V</tex> вернул '''true''', <tex>P</tex> должен посылать такие <tex>A_i</tex>, чтобы выполнялись все проверяемые условия. Посмотрим на то, что он может послать:
:'''Шаг 0'''
:Так как количество наборов, удовлетворяющих <tex>\varphi</tex>, не равно <tex>k</tex>, то <tex>\mathit{Prover}P</tex> не может послать правильное <tex>A_0</tex>, поскольку в этом случае не выполнится условие <tex>A_0(0) + A_0(1) = k</tex>. Поэтому он посылает не <tex>A_0</tex>, а некое <tex>\tilde{A}_0</tex>.
:<tex>\ldots</tex>
:'''Шаг i'''
|statement=<tex>\mathrm{coNP} \subset \mathrm{IP}</tex>.
|proof=
[[Сведение_относительно_класса_функций._Сведение_по_Карпу._Трудные_и_полные_задачи|Сведём ]] [[Теорема_Бермана_—_Форчуна | язык <tex>\mathrm{TAUT}</tex>]] к языку <tex>\mathrm{\#SAT}</tex> следующим образом: <tex>\varphi \mapsto \langle \varphi, 2^k \rangle </tex>, где <tex>k</tex> — количество различных переменных в формуле <tex>\varphi</tex>.
Очевидно, что <tex>\varphi \in \mathrm{TAUT} \Leftrightarrow \langle \varphi, 2^k \rangle \in \mathrm{\#SAT}</tex>.
* [[Вероятностные вычисления. Вероятностная машина Тьюринга]]
* [[Теорема Бермана — Форчуна]]
* [[Классы NP, coNP, Σ₁, Π₁]]
[[Категория: Теория сложности]]
[[Категория: Вероятностные сложностные классы]]
[[Категория: Интерактивные протоколы]]
