Décider le bit le plus important de la multiplication binaire

Je souhaite déterminer la complexité du problème de décision suivant: étant donné deux entiers $l_1$ et $l_2$ (chacun avec au plus m bits), décider si le bit le plus significatif de la multiplication $l_1 \cdot l_2$ est 1 (où le résultat est imprimé en bits de 2 m avec éventuellement des 0 en tête)?

Quelques informations sur le problème: Évidemment, ce problème est un cas particulier de multiplication binaire qui demande si le ème bit de la multiplication est 1. Dans leur article, Circuits de seuil uniformes à profondeur constante pour la division et itérés multiplication , Hesse, Allender et Barrington prouvent que la multiplication itérée (et donc binaire) est en - uniforme . De plus, il semble bien connu que la multiplication binaire est déjà $i$ $l_1 \cdot l_2$ $\mathsf{DLogTime}$ $\mathsf{TC}^0$ -uniforme -hard. Cependant, je n'ai pas pu trouver de source particulière prouvant ce résultat de dureté. En tant que non-expert en complexité de circuit, j'apprécierais également un pointeur sur ce résultat de dureté générale. Enfin, en supposant que la multiplication binaire est -uniforme -hard, ma question peut également être lue comme suit: Reste-t-elle -uniforme $\mathsf{DLogTime}$ $\mathsf{TC}^0$ $\mathsf{DLogTime}$ $\mathsf{TC}^0$ $\mathsf{DLogTime}$ $\mathsf{TC}^0$ -dur si nous voulons décider uniquement le bit de multiplication binaire le plus significatif?

MISE À JOUR: La réponse de Kaveh clarifie pourquoi la multiplication binaire est -hard (réduction de COUNT). La complexité précise de décider du bit de multiplication binaire le plus significatif reste ouverte (et la prime est pour cette question). $\mathsf{TC}^0$

cc.complexity-theory circuit-complexity Heyheyhey
la source

Il y a une preuve dans le livre de la complexité descriptive iirc. Je ne sais pas ce que vous entendez par le bit le plus significatif étant un, c'est toujours un par définition.

Kaveh

Ceci est juste une blague de votre professeur: les bits sont 0 ou 1, et le bit le plus significatif est le bit non 0 dans la position la plus élevée. Il est égal à 1 par définition (sauf si l'un des facteurs

est nul).

l_{1}

$l_1$

l_{2}

$l_2$

Gamow

@Kaveh Merci pour la référence: je vais le vérifier. Désolé pour la confusion concernant le bit le plus significatif. Je suppose implicitement que le résultat est imprimé en 2m-1 bits et si nécessaire avec des 0 en tête.

Heyheyhey

@Kaveh: Dans le Descriptive Complexity Book, seule la limite supérieure est mentionnée. Cependant, je n'ai rien trouvé concernant la dureté de la multiplication binaire.

Heyheyhey

Vous écrivez: "De plus, il semble bien connu que la multiplication binaire est déjà

- uniforme

-hard." Pourquoi semble-t-il ainsi? Je sais que la multiplication binaire n'est pas en

, et c'est tout ce qui m'intéresse actuellement.

D L o g T i m e

$\mathsf{DLogTime}$

{T C}^{0}

$\mathsf{TC}^0$

{A C}^{0}

$\mathsf{AC}^0$

Thomas Klimpel

La multiplication est terminée pour et c'est un résultat bien connu. La réduction est de Count (nombre de 1 bits dans un nombre binaire). La comparaison des nombres binaires est en donc est réductible en . $\mathsf{TC}^0$ $\mathsf{AC^0}$ $\mathsf{Majority}$ $\mathsf{Count}$

Pour réduire à procédez comme suit: considérez que l'entrée est . Insérez 0 entre s et appelez-le . Multipliez-le par qui est comme sauf que s y est remplacé par 1s. Sélectionnez . Le nombre dans la section centrale d' est la réponse. La réduction est en $\mathsf{Count}$ $\mathsf{Mult}$ $a_0a_1\ldots a_n$ $k$ $a_i$ $a$ $b$ $a$ $a_i$ $k>3n$ $ab$ $\mathsf{FO}$ et montre que . $\mathsf{Count} \in \mathsf{FO(Mult)}$

Kaveh
la source

Merci pour les réponses! Oui, cela vérifie que la multiplication binaire est terminée pour TC0. Quant à la partie la plus importante, il reste quelques problèmes. Le bit le plus significatif de la multiplication (111 x 111) = 110001 est 1, et pour celui-ci (100 x 100) = 010000, il est 0. Notez que les bits les plus significatifs des multiplicandes sont les mêmes dans les deux cas. Par conséquent, je ne pense pas qu'en général, il suffise d'additionner les bits les plus significatifs. Suis-je en train de manquer quelque chose?

Heyheyhey

, le MSB de

est 0, et le MSB

est 1, même si

ne peut différer un bit, le moins significatif.

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$

Emil Jeřábek

L'édition n'est pas correcte. Puisque nous ajoutons m nombres, il peut ne pas y avoir un seul bit de report, mais log m. Il est alors beaucoup plus difficile de décider de sa propagation.

Emil Jeřábek

En effet, sans tenir compte de tout le reste: calculer l'exécution d'une position unique (disons quelque part au milieu) équivaut déjà à Count, d'où TC ^ 0-complete.

Emil Jeřábek

@Heyheyhey, la formule que j'ai écrite est FO et donc en uniforme AC0.

Kaveh

Décider le bit le plus important de la multiplication binaire

Réponses: