7 ms·
Yes, the worst-case complexity is exponential in N, but the wording in the article could lead you to believe that no explicit exponential bound is known, which
by fdej 5y ago
Yes, the worst-case complexity is exponential in N, but the wording in the article could lead you to believe that no explicit exponential bound is known, which is false.
- adgjlsfhk1 5y agoThis is false. PSPACE is in EXPTIME.
- tgflynn 5y agoDo you have a reference for that claim ?
- fdej 5y agoCorrecting 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 agoThe 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.