271
правка
Изменения
Нет описания правки
{{Теорема
|statement=
|proof=
Пусть <tex> L \in PSIZE </tex> схемная сложность полином, x {{---}} входная строка. Тогда существуют логические схемы <tex> \exists 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>
}}
{{Теорема
|statement=
<tex> P/poly \subset PSIZE</tex> схемная сложность полином.
|proof=
Пусть <tex> L \in P/poly </tex>. Тогда существуют <tex> a_0, a_1, .. , a_n, .. </tex> {{---}} подсказки. Зафиксируем n. Числу соответствует логическая схема <tex> C_n </tex>. Запишем программу p в виде логической схемы, которая принимает на вход слово длины n и подсказку <tex> a_n </tex>, за счет чего распознаваться будут только слова из языка. Зашьем подсказку в самой схеме, теперь она принимает только слова длины n и определяет их принадлежность языку.
}}
