211
правок
Изменения
м
→Теоремы
|proof=
Докажем, что <tex> \mathrm{PSIZE} \subset \mathrm{P/poly} </tex>. <br>
Пусть <tex> L \in \mathrm{PSIZE} </tex>, <tex> x </tex> {{---}} входная строка. Тогда для <tex> L </tex> существуют логические схемы <tex> C_0, C_1, .., C_n, .. </tex>. В качестве подсказки для <tex> x </tex> предоставим логическую схему <tex> C_{|x|} </tex>. Программа <tex> p </tex> получает на вход <tex> x </tex> и <tex> C_{|x|} </tex> и возвращает значение, вычисляемое <tex> C_{|x|} </tex> для входа <tex> x </tex>. Запишем программу
<tex> p(x, C_{|x|}) </tex>:
'''return''' <tex>C_{|x|}(x) </tex>
