Схемная сложность и класс 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:
|