40
правок
Изменения
Новая страница: «==Класс IP== {{Определение |definition = <tex>IP[f] = \{L|\exists \langle V, P \rangle : </tex> <br/> <tex> 1) \forall x \in L \Rightarrow P(V(x) ...»
==Класс IP==
{{Определение
|definition =
<tex>IP[f] = \{L|\exists \langle V, P \rangle : </tex> <br/>
<tex> 1) \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex><br/>
<tex> 2) \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex><br/>
<tex> 3) </tex> Число раундов интерактивного протокола <tex> f(n), n = |x| </tex><br/>
}}
{{Теорема
|statement=<tex>\mathrm{NP} \subset \mathrm{IP[1]}</tex>
|proof=
*<tex>\mathrm{NC^i} \subset \mathrm{AC^i}</tex> <br/>
Это понятно из определения <tex>\mathrm{NC^i}</tex> и <tex>\mathrm{AC^i}</tex>. <br/>
*<tex>\mathrm{AC^i} \subset \mathrm{NC^{i+1}}</tex> <br/>
Пусть <tex>L \in \mathrm{AC^i}</tex>. <tex>L</tex> распознается семейством схем <tex>C_n</tex> полиномиального размера. Значит, степень входа элементов схемы <tex>C_n</tex> — это полином от <tex>n</tex>. Заменим элементы схемы <tex>C_n</tex> элементами со степенью входа не более двух следующим образом: <br/>
[[Файл:circuit.jpg]]
При замене каждого такого элемента глубина схемы увеличивается не более чем в <tex>log_2 r(n) = O(log(n))</tex>, а так как изначально глубина схемы была <tex>O(log^i(n))</tex>, то после замены всех элементов глубина схемы станет <tex>O(log^i(n)) \cdot O(log(n)) = O(log^{i+1}(n))</tex>.<br> Так как при замене элемента мы добавляем не более <tex>r(n)</tex> элементов, а изначально размер схемы был полиномиальным и каждый ее элемент мы заменили на полином элементов, то после всех замен размер схемы остался полиномиальным.
}}
{{Определение
|definition =
<tex>IP[f] = \{L|\exists \langle V, P \rangle : </tex> <br/>
<tex> 1) \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex><br/>
<tex> 2) \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex><br/>
<tex> 3) </tex> Число раундов интерактивного протокола <tex> f(n), n = |x| </tex><br/>
}}
{{Теорема
|statement=<tex>\mathrm{NP} \subset \mathrm{IP[1]}</tex>
|proof=
*<tex>\mathrm{NC^i} \subset \mathrm{AC^i}</tex> <br/>
Это понятно из определения <tex>\mathrm{NC^i}</tex> и <tex>\mathrm{AC^i}</tex>. <br/>
*<tex>\mathrm{AC^i} \subset \mathrm{NC^{i+1}}</tex> <br/>
Пусть <tex>L \in \mathrm{AC^i}</tex>. <tex>L</tex> распознается семейством схем <tex>C_n</tex> полиномиального размера. Значит, степень входа элементов схемы <tex>C_n</tex> — это полином от <tex>n</tex>. Заменим элементы схемы <tex>C_n</tex> элементами со степенью входа не более двух следующим образом: <br/>
[[Файл:circuit.jpg]]
При замене каждого такого элемента глубина схемы увеличивается не более чем в <tex>log_2 r(n) = O(log(n))</tex>, а так как изначально глубина схемы была <tex>O(log^i(n))</tex>, то после замены всех элементов глубина схемы станет <tex>O(log^i(n)) \cdot O(log(n)) = O(log^{i+1}(n))</tex>.<br> Так как при замене элемента мы добавляем не более <tex>r(n)</tex> элементов, а изначально размер схемы был полиномиальным и каждый ее элемент мы заменили на полином элементов, то после всех замен размер схемы остался полиномиальным.
}}
