271
правка
Изменения
→Теоремы
Докажем, что <tex> \mathrm{P/poly} \subset \mathrm{PSIZE} </tex>. <br>
Пусть <tex> L \in \mathrm{P/poly} </tex>, <tex> x </tex> {{---}} входная строка. Тогда для <tex> L </tex> существуют подсказки <tex> a_0, a_1, .. , a_n, .. </tex>. Программа <tex> p </tex> по входу <tex> x </tex> и подсказке <tex> a_{|x|} </tex> определяет принадлежность <tex> x </tex> языку <tex> L </tex>. Зафиксируем длину входной строки <tex> x </tex> как <tex> n </tex>. Теперь запишем <tex> p </tex> в виде логической схемы <tex> C_m </tex> ( <tex> m = n + |a_n| </tex>), которая принимает на вход слова длины <tex> n </tex> и подсказку <tex> a_n </tex>. Полученная схема будет полиномиального размера. Зашьем подсказку в самой схеме, то есть впишем в нее значения битов подсказки. Получим схему <tex> C_n </tex> полиномиального размера, принимающую слова длины <tex> n </tex> и определяющую их принадлежность языку <tex> L </tex>. Такие схемы можно получить для любой длины входа. Значит, <tex> \mathrm{P/poly} \subset \mathrm{PSIZE} </tex>.
}}
{{Теорема
|statement=
<tex> \mathrm{P/poly} </tex> содержит неразрешимые языки.
|proof=
Пусть <tex> L \subset \{0, 1\}^* </tex> {{---}} произвольный неразрешимый язык.
Пусть <tex> A = \{1^n | </tex> бинарное представление <tex> n </tex> принадлежит <tex> L \} </tex>.
<tex> \mathrm{P/poly} </tex> позволяет разрешить <tex> A </tex>. В качестве подсказки <tex> a_n </tex> для входа <tex> x </tex> будем передавать единицу, если <tex> 1^n \in A </tex>, иначе ноль. <br>
Таким образом, <tex> \mathrm{P/poly} </tex> содержит неразрешимые языки.
}}
[[Категория: Теория сложности]]
