Изменения

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

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

1 байт добавлено, 21:06, 24 апреля 2012
Определения
Пусть 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>.
}}
271
правка

Навигация