2
$\begingroup$

Randal Bryant developed an exponential size lower bound for any BDD encoding the middle bit output of the multiplication function, regardless of variable permutation.

But at the same time the multiplication function is decidable in logarithmic space. Of course related to P versus NP, the lower bounds complexity of its inverse function is currently unknown. Having an efficient BDD encoding for multiplication also provides a mechanism for efficient factoring, so I understand that this would seem implausible.

However, if a function belongs to L (such as multiplication or so I think), it most certainly belongs to L/Poly which is (to my understanding) the class of polynomial sized BDDs.

From what I can discern, Bryant's proof relies on communication complexity rather than crypto-hardness assumptions or building upon mainstream conjecture. So what's going on here that seems a blatant contradiction in known lower bounds?

For some related background see this post: https://cstheory.stackexchange.com/questions/3462/most-significant-bit-of-integer-multiplication-and-binary-decision-diagrams

Improve this question
$\endgroup$
2
  • $\begingroup$ Do you have a more precise formulation of the statement that multiplication is decidable in logarithmic space? And a reference for that result? Is the result saying that the language $\{(x,y,z) : xy=z\}$ is in $L$? That corresponds to checking the output of a multiplication algorithm. Note that checking that an answer is correct can sometimes be easier than computing the correct answer (see, e.g., the P vs NP question). When reasoning about complexity classes below P, small details of how the problem is represented/encoded as a language can make a difference. $\endgroup$
    – D.W. ♦
    Feb 23, 2017 at 16:45
  • $\begingroup$ Please don't vandalize your questions. $\endgroup$
    – Robert Columbia
    Nov 28, 2018 at 2:43

1 Answer 1

Reset to default
0
$\begingroup$

I think the resolution to the paradox comes from looking more carefully what is meant when we say that multiplication can be performed in logarithmic space, and looking more carefully at what we mean by a BDD.

Suppose we want to multiply two $n$-bit numbers $a,b$, and suppose the two numbers $a,b$ are stored in read-only memory. Then we can calculate any desired bit of the product using only $O(\lg n)$ additional bits of space. However, this fundamentally requires us to have (read-only) access to the numbers being multiplied.

(Take a look at the formula in Wikipedia for $r_i$: $r_i$ depends on $a$, $b$, and $c_{i-1}$. The carry $c_{i-1}$ needs only $O(\lg n)$ bits of space to store. However, just storing the carry alone is not enough. We also need to have the numbers $a,b$ stored, and that requires $\Theta(n)$ bits of storage.)

In short, multiplying two numbers takes $\Theta(n)$ bits (read-only) for the numbers being multiplied and $\Theta(\lg n)$ bits (read-write) of additional storage. This does prove that multiplication is in $L$. However, it doesn't prove that there is a polynomial-size BDD for multiplication.

First, let's understand what we mean by BDD. There are many types of BDD, but the most relevant one here is the notion of a ROBDD (read-once binary decision diagram). A ROBDD is allowed to read each bit of the input only once. Normally, BDD means a ROBDD: for a reference, see, e.g., the Wikipedia article on BDDs, which writes "In popular usage, the term BDD almost always refers to Reduced Ordered Binary Decision Diagram (ROBDD". Moreover, the lower bound for the size of a BDD for multiplication is actually a lower bound on the size of a ROBDD for multiplication. Therefore, in this answer I'll assume BDD means ROBDD.

Now, here's why the above algorithm doesn't prove there is a polynomial-size (RO)BDD for multiplication. Given an algorithm with space complexity $s$ and time complexity $t$, you can construct a BDD with something like $2^s \times t$ nodes (but here $s$ must include all input bits that might be read more than once, as well as all additional storage). This means that the number of nodes in a BDD could be as much as exponential in $s$. In the case of multiplication, we have $s = \Theta(n+\lg n) = \Theta(n)$, so from the existence of the multiplication algorithm above, all we can conclude is that the size of the BDD could be (at most) exponential in $n$. This isn't enough to show that there exists a polynomial-size BDD.

What about L vs L/poly vs BDDs? I don't think it's true that just because a problem is in L/poly, that means it has a polynomial-size BDD.

Roughly speaking (ignoring uniformity vs non-uniformity), a problem is in L or L/poly if there is an algorithm that has read-only access to the inputs and uses only $O(\lg n)$ additional bits of (read-write) storage. If we also knew that this algorithm reads each bit of its input only once, then that would imply that there is a polynomial-size (RO)BDD for the problem. But if the algorithm scans back and forth over the input bits, reading them many times, then I don't think there necessarily exists a polynomial-sized (RO)BDD for the problem. At least, I don't know of any result that implies that. I could be missing something.

I know Wikipedia says that L/poly is "a complexity class that captures the complexity of problems with polynomially sized BDDs". I am not sure that is exactly correct.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Why does that mean "that the number of nodes in a BDD could be as much as exponential in the number of bits read"? ​ The product you wrote is just exponential in the space complexity. ​ "BDD means a ROBDD" is the important part of this answer, since it goes against the obvious meaning. ​ ​ ​ ​ $\endgroup$
    – user12859
    Feb 24, 2017 at 4:17
  • $\begingroup$ How do you show the collapse from polylogarithmic storage to logarithmic storage? ​ ​ $\endgroup$
    – user12859
    Feb 24, 2017 at 4:18
  • $\begingroup$ @RickyDemer, Thanks for all the feedback and corrections! 1. Yes, you're absolutely right. Sorry about that. I meant "space complexity". Fixed. 2. I've added some more to my answer to emphasize that, and provide a reference for my statement that BDD normally means ROBDD, and why that's appropriate here. 3. Oops. You're absolutely right. I didn't actually mean polylog; I meant log. My mistake. Fixed. Does it look good now? $\endgroup$
    – D.W. ♦
    Feb 24, 2017 at 10:36
  • $\begingroup$ The space complexity is $\Theta(\log(n))$, not $\Theta(n)$. ​ I suggest moving the BDD discussion to before that, and then specifying that $s$ needs to account for input bits which might be read more than once. ​ ​ ​ ​ $\endgroup$
    – user12859
    Feb 24, 2017 at 11:33
  • $\begingroup$ @RickyDemer, OK. Good point. Better now? $\endgroup$
    – D.W. ♦
    Feb 24, 2017 at 11:53

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.