Выбор наиболее значимого бинарного умножения

Я заинтересован в определении сложности следующей задачи решения: учитывая два целых числа и (каждое из которых содержит не более m бит), решить, является ли старший значащий бит умножения 1 (где результат печатается в 2м битах с возможно ведущими 0)? $l_1$ $l_2$ $l_1 \cdot l_2$

Некоторые советы по проблеме: Очевидно, что эта проблема является частным случаем двоичного умножения , который спрашивает , является ли -й бит умножения равен 1. В своей работе, Uniform постоянной глубины пороговые схемы для разделения и итерация Умножение , Гессе, Аллендер и Баррингтон доказывают, что итеративное (и, следовательно, бинарное) умножение в - равномерно . Более того, кажется общеизвестным, что двоичное умножение уже является $i$ $l_1 \cdot l_2$ $\mathsf{DLogTime}$ $\mathsf{TC}^0$ -равномерный -Жесткими. Тем не менее, я не смог найти конкретный источник, подтверждающий этот результат. Как не специалист в сложности схемы, я также был бы признателен за указание на этот общий результат твердости. Наконец, предполагая, что двоичное умножение -равномерно -hard, мой вопрос также можно прочитать так: остается ли оно -равномерно $\mathsf{DLogTime}$ $\mathsf{TC}^0$ $\mathsf{DLogTime}$ $\mathsf{TC}^0$ $\mathsf{DLogTime}$ $\mathsf{TC}^0$ -Твердо, если мы хотим решить только самый значимый бит двоичного умножения?

ОБНОВЛЕНИЕ: ответ Каве разъясняет, почему двоичное умножение является жестким (сокращение от COUNT). Точная сложность определения наиболее значимого бита двоичного умножения остается открытой (и награда за этот вопрос). $\mathsf{TC}^0$

cc.complexity-theory circuit-complexity Эй Эй Эй
источник

В книге «Описательная сложность» есть доказательство iirc. Я не уверен, что вы подразумеваете под самым значительным, будучи единым, оно всегда одно по определению.

Каве

Это просто шутка вашего учителя: биты равны 0 или 1, и самый важный бит - это ненулевой бит в старшей позиции. По определению он равен 1 (если только один из факторов

равен нулю).

l_{1}

$l_1$

l_{2}

$l_2$

Гамов

@Kaveh Спасибо за ссылку: я проверю это. Извините за путаницу относительно самого значительного бита. Я неявно предполагаю, что результат печатается в битах 2m-1 и, если необходимо, с начальными 0.

Хейхейхей

@Kaveh: в книге описательной сложности упоминается только верхняя граница. Однако я не смог найти ничего, касающегося сложности двоичного умножения.

Хейхейхей

Вы пишете: «Более того, кажется, хорошо известно, что двоичное умножение - это уже

- равномерный

-хард». Почему это так кажется? Я знаю, что двоичное умножение не в

, и это все, что меня волнует в настоящее время.

D L o g T i m e

$\mathsf{DLogTime}$

{T C}^{0}

$\mathsf{TC}^0$

{A C}^{0}

$\mathsf{AC}^0$

Томас Климпел

Умножение завершено для и это хорошо известный результат. Сокращение от Count (количество 1 бит в двоичном числе). Сравнение двоичных чисел в поэтому сводится к . $\mathsf{TC}^0$ $\mathsf{AC^0}$ $\mathsf{Majority}$ $\mathsf{Count}$

Для уменьшения к сделать следующим образом : рассмотрит вход . Вставьте 0 между s и назовите его . Умножьте его на который похож на за исключением того, что s в нем заменены на 1s. Выберите . Число в средней части ответ. Снижение в $\mathsf{Count}$ $\mathsf{Mult}$ $a_0a_1\ldots a_n$ $k$ $a_i$ $a$ $b$ $a$ $a_i$ $k>3n$ $ab$ $\mathsf{FO}$ и показывает, что . $\mathsf{Count} \in \mathsf{FO(Mult)}$

Кава
источник

Спасибо за ответы! Да, это подтверждает, что двоичное умножение завершено для TC0. Что касается самого значительного, остаются некоторые проблемы. Самый старший бит умножения (111 x 111) = 110001 равен 1, а для этого (100 x 100) = 010000 он равен 0. Обратите внимание, что старшие значащие биты мультипликаторов одинаковы в обоих случаях. Поэтому я не думаю, что в общем случае достаточно сложить наиболее значимые биты. Я что-то пропустил?

Хейхейхей,

Если

, то старший бит

равен 0, а старший бит

равен 1, даже если

могут отличаться только в один, наименее значимый, бит.

x = ⌊ 2^{n + 1 / 2} ⌋

$x=\lfloor2^{n+1/2}\rfloor$

y = ⌈ 2^{n + 1 / 2} ⌉

$y=\lceil2^{n+1/2}\rceil$

x^{2}

$x^2$

y^{2}

$y^2$

x

$x$

y

$y$

Эмиль Йержабек

Редактирование не является правильным. Так как мы добавляем m чисел, может быть не один бит переноса, а log m. Решить, сколько из них размножается, гораздо сложнее.

Эмиль Йержабек

Действительно, не обращая внимания на все остальное: вычисление выполнения одной позиции (скажем, где-то посередине) уже эквивалентно Count, следовательно, TC ^ 0-complete.

Эмиль Йержабек

@Heyheyhey, формула, которую я написал, является FO и, следовательно, в форме AC0.

Каве

Выбор наиболее значимого бинарного умножения

Ответы: