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

Для вычисления функции голосования существует схема:

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

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

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

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

размера

и глубины $O(\log _2 n \cdot \log _2 \log _2 n)$ (Верный ответ)

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

Для вычисления функции голосования существует схема:

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

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

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

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

Схема "ИЛИ - НЕ" имеет:

Схема "И - НЕ" имеет:

Схема "ИСКЛЮЧАЮЩЕЕ - ИЛИ" имеет:

Две интерпретации - изоморфны, если между ними существует:

Если B - полный базис, то существует C - const

Для всякой формулы F сигнатуры $\left\langle { = , < ,0,1, + ,x} \right\rangle$ существует бескванторная формула, задающая F на R - это:

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

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

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