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