10
$\begingroup$

I am interested in determining the complexity of the following decision problem: Given two integers $l_1$ and $l_2$ (each with at most m bits), decide whether the most significant bit of the multiplication $l_1 \cdot l_2$ is 1 (where the result is printed in 2m bits with possibly leading 0's)?

Some background on the problem: Obviously, this problem is a special case of binary multiplication that asks whether the $i$-th bit of the multiplication $l_1 \cdot l_2$ is 1. In their paper, Uniform constant-depth threshold circuits for division and iterated multiplication, Hesse, Allender and Barrington prove that iterated (and thus binary) multiplication is in $\mathsf{DLogTime}$-uniform $\mathsf{TC}^0$. Moreover, it seems to be well-known that binary multiplication is already $\mathsf{DLogTime}$-uniform $\mathsf{TC}^0$-hard. However, I was not able to find a particular source proving this hardness result. As a non-expert in circuit complexity, I would also appreciate a pointer to this general hardness result. Finally, assuming that binary multiplication is $\mathsf{DLogTime}$-uniform $\mathsf{TC}^0$-hard, my question can also be read as: Does it remain $\mathsf{DLogTime}$-uniform $\mathsf{TC}^0$-hard if we want to decide only the most significant bit of binary multiplication?

UPDATE: Kaveh's answer clarifies why binary multiplication is $\mathsf{TC}^0$-hard (reduction from COUNT). The precise complexity of deciding the most significant bit of binary multiplication remains open (and the bounty is for this question).

Improve this question
$\endgroup$
7
  • $\begingroup$ There is a proof in Descriptive Complexity book iirc. Am not sure what you mean by most significant bit being one, it always is one by definition. $\endgroup$
    – Kaveh
    Aug 28, 2017 at 13:13
  • $\begingroup$ This is just a joke of your teacher: Bits are 0 or 1, and the most significant bit is the non-0 bit in the highest position. It equals 1 by definition (unless one of the factors $l_1$ and $l_2$ is zero). $\endgroup$
    – Gamow
    Aug 28, 2017 at 13:16
  • $\begingroup$ @Kaveh Thanks for the reference: I'll check it out. Sorry for the confusion regarding the most significant bit. I am implicitly assuming that the result is printed in 2m-1 bits and if necessary with leading 0's. $\endgroup$
    – Heyheyhey
    Aug 28, 2017 at 13:43
  • $\begingroup$ @Kaveh: In the Descriptive Complexity Book, only the upper bound is mentioned. I could not find anything regarding hardness of binary multiplication, though. $\endgroup$
    – Heyheyhey
    Aug 28, 2017 at 14:00
  • $\begingroup$ You write: "Moreover, it seems to be well-known that binary multiplication is already $\mathsf{DLogTime}$-uniform $\mathsf{TC}^0$-hard." Why does it seem so? I know that binary multiplication is not in $\mathsf{AC}^0$, and that is all I currently care about. $\endgroup$
    – Thomas Klimpel
    Aug 28, 2017 at 21:13

1 Answer 1

Reset to default
6
$\begingroup$

Multiplication is complete for $\mathsf{TC}^0$ and this is a well know result. The reduction is from Count (number of 1 bits in a binary number). Comparison of binary numbers is in $\mathsf{AC^0}$ so $\mathsf{Majority}$ is reducible to $\mathsf{Count}$.

To reduce $\mathsf{Count}$ to $\mathsf{Mult}$ do as follows: consider input is $a_0a_1\ldots a_n$. Insert $k$ 0s between $a_i$s and call it $a$. Multiply it with $b$ which is like $a$ except that $a_i$s in it are replaced with 1s. Pick $k>3n$. The number in the middle section of $ab$ is the answer. The reduction is in $\mathsf{FO}$ and shows that $\mathsf{Count} \in \mathsf{FO(Mult)}$.

Improve this answer
$\endgroup$
11
  • 1
    $\begingroup$ Thanks for the answers! Yes, this verifies that binary multiplication is complete for TC0. As for most significant bit, there are some issues remaining. The most significant bit of the multiplication (111 x 111) = 110001 is 1, and for this one (100 x 100)= 010000, it is 0. Note that the most significant bits of the multiplicands are the same in both cases. Therefore, I do not think that, in general, it is sufficient to add up the most significant bits. Am I missing something? $\endgroup$
    – Heyheyhey
    Aug 29, 2017 at 5:57
  • 1
    $\begingroup$ If $x=\lfloor2^{n+1/2}\rfloor$ and $y=\lceil2^{n+1/2}\rceil$, then the MSB of $x^2$ is 0, and the MSB of $y^2$ is 1, even though $x$ and $y$ may only differ in one, least significant, bit. $\endgroup$
    – Emil Jeřábek
    Aug 29, 2017 at 6:53
  • 3
    $\begingroup$ The edit is not correct. Since we are adding m numbers, there may not be just one bit of carry, but log m. Deciding how much of it propagates is then much more difficult. $\endgroup$
    – Emil Jeřábek
    Aug 30, 2017 at 6:19
  • 1
    $\begingroup$ Indeed, disregarding everything else: computing the carry out of a single position (say, somewhere in the middle) is already equivalent to Count, hence TC^0-complete. $\endgroup$
    – Emil Jeřábek
    Aug 30, 2017 at 6:23
  • 1
    $\begingroup$ @Heyheyhey, the formula I wrote is FO and therefore in uniform AC0. $\endgroup$
    – Kaveh
    Aug 30, 2017 at 10:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.