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