Языки и исчисления

Сложность большинства булевой -местной функций при наибольшем размере их схем:

(Отметьте один правильный вариант ответа.)

Варианты ответа

равна

при

и больших

не меньше

при

и больших

(Верный ответ)

не меньше

при

и больших

Похожие вопросы

Сложность любой булевой

-местной функций при наибольшем размере

их схем:

При некотором C > 0

сложность большинства булевых

-местных функций:

Верно утверждение для любой булевой функции

от

аргументов:

Количество всех различных

-местных схем размера

оценивается:

Контрпример к секвенции $A \mapsto B$ будет контрпримером к формуле ( $\wedge A$ - конъюнкция, $\vee A$ - дизъюнкция формул из А)

Вычитание двух

-разрядных двоичных чисел по модулю 2^n

выполнима схема:

Количество всех

-местных булевых функций равно:

Если

- минимальная глубина схемы, вычисляющая функцию

, то:

Верна теорема для любой булевой функции