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.
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.
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.