Схемная сложность и класс P/poly
Версия от 16:12, 14 апреля 2012; Vincent (обсуждение | вклад) (Новая страница: «{{Определение |definition= <tex>P/poly=\{L | \forall n </tex> существует логическая схема <tex> C_n </tex> с <tex> n </tex> ...»)
Определение: |
| существует логическая схема с входами и одним выходом такая, что:
Определение: |
Пусть C — сложностный класс, f — функция. Тогда
| существуют программа p, удовлетворяющая ограничениям C: