Изменения

<tex> P \subset P/poly PSIZE </tex>.

Пусть <tex> L \in P \Rightarrow \exists </tex> . Тогда существует машина Тьюринга m такая, что <tex> L(m)=распознающая язык L </tex>. Составим логическую схему для m, как мы сделали в [[Примеры_NP-полных_языков._Теорема_Кука|теореме Кука]], ее размеры ограничены полиномом, она допускает только слова из языка. Отсюда следует, что <tex> P \subset P/poly PSIZE </tex>.

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