Изменения

Перейти к: навигация, поиск

Схемная сложность и класс P/poly

8 байт убрано, 16:51, 31 мая 2012
Определения
{{Определение
|definition=
Пусть <tex> \mathrm{C} </tex> {{---}} сложностный класс, <tex> \mathrm{f} </tex> {{---}} функция. Тогда <tex> \mathrm{C/f} = \{L| </tex> существуют подсказки <tex> a_0, a_1, .. , a_n, .. </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>.
271
правка

Навигация