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

Для умножения двух -разрядных двоичных чисел существует схема:

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

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

размера $O\left( {n^{\log _2 3} } \right)$ и глубины $O(\log _2 n)$ (Верный ответ)

размера $O(\log _2^2 n)$ и глубины $O\left( {n^{\log _2 3} } \right)$

размера $o(\log _2 n)$ и глубины o(n)

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

Для умножения двух

-разрядных двоичных чисел существует схема:

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

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

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

Для сложения двух

-разрядных двоичных чисел:

Для сложения двух

-разрядных двоичных чисел:

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

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

их схем:

Сложность большинства булевой

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

их схем:

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

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

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

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

от

аргументов:

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

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

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

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