4 ms·

Do you have a reference for that claim ?

• fdej 5y ago
  Correcting myself, the bound is worse than exponential (so read "at least exponential in N"), but the point I wanted to make is that it is explicit. Again, this follows from the general theory of algebraic numbers: the degree and height of a sum, product or root of algebraic numbers can be bounded explicitly (resultants + Mignotte bound for factors), and finally root separation bounds can be applied to the resulting polynomial.
  • tgflynn 5y ago
    The author says that this problem is in PSPACE. That's not obvious to me because I don't know how you sum arbitrarily long binary numbers in polynomial space. However if you and he are both right that would suffice to prove P != PSPACE, so this problem is potentially very important. Unfortunately I don't even know what this kind of problem is called, which makes googling a bit difficult.