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