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