editor
177
правок
Изменения
м
→Определения
#Input <tex> (C_n) = n </tex>;
#Output <tex> (C_n) = 1 </tex>;
#<tex>x \in L \iff Leftrightarrow C_{|x|}(x) = 1 \}</tex>.
}}
Пусть <tex> \mathrm{C} </tex> {{---}} сложностный класс, <tex> 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 f(i) </tex>;
#<tex> x \in L \iff Leftrightarrow p(x, a_{|x|})=1 \}</tex>.
}}
