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