271
правка
Изменения
Нет описания правки
== Определения ==
{{Определение
|definition=
#<tex>|a_i| \leqslant f(i) </tex>;
#<tex> x \in L \iff p(x, a_{|x|})=1 </tex>.
}}
== Теоремы ==
{{Теорема
|statement=
<tex> P \subset P/poly </tex>.
|proof=
<tex> L \in P \Rightarrow \exists </tex> Машина Тьюринга m такая, что <tex> L(m)=L </tex>. В [[Примеры_NP-полных_языков._Теорема_Кука|теореме Кука]] мы показали, что для машины Тьюринга можно составить логическую схему. Отсюда следует, что <tex> P \subset P/poly </tex>.
}}
