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