271
правка
Изменения
Новая страница: «{{Определение |definition= <tex>P/poly=\{L | \forall n </tex> существует логическая схема <tex> C_n </tex> с <tex> n </tex> ...»
{{Определение
|definition=
<tex>P/poly=\{L | \forall n </tex> существует логическая схема <tex> C_n </tex> с <tex> n </tex> входами и одним выходом такая, что:
#размеры <tex> C_n \leqslant p(n)</tex>;
#<tex>x \in L \iff C_{|x|}(x) = 1 \}</tex>.
}}
{{Определение
|definition=
Пусть C {{---}} сложностный класс, f {{---}} функция. Тогда <tex> C/f = \{L| </tex> существуют <tex> a_0, a_1, .. , a_n, .. , </tex> программа p, удовлетворяющая ограничениям C:
#<tex>|a_i| \leqslant f(i) </tex>;
#<tex> x \in L \iff p(x, a_{|x|})=1 </tex>.
}}
|definition=
<tex>P/poly=\{L | \forall n </tex> существует логическая схема <tex> C_n </tex> с <tex> n </tex> входами и одним выходом такая, что:
#размеры <tex> C_n \leqslant p(n)</tex>;
#<tex>x \in L \iff C_{|x|}(x) = 1 \}</tex>.
}}
{{Определение
|definition=
Пусть C {{---}} сложностный класс, f {{---}} функция. Тогда <tex> C/f = \{L| </tex> существуют <tex> a_0, a_1, .. , a_n, .. , </tex> программа p, удовлетворяющая ограничениям C:
#<tex>|a_i| \leqslant f(i) </tex>;
#<tex> x \in L \iff p(x, a_{|x|})=1 </tex>.
}}
