[kraghen]

The definition of "basic step", which includes arithmetic on unbounded integers, is suspicious. And I don't see any attempt at establishing an upper bound on the size of coefficients. I wouldn't be surprised if they grow exponentially.

[ogogmad]

This might be it. Good catch. A machine that can perform all integer arithmetic operations (+, -, *) in constant time can solve all problems in PSPACE in polynomial time.

[silasdavis]

Yes I think this is where NP is hiding.

[bodhiandphysics]

We’re lucky he didn’t claim p=PSPACE!

[teraflop]

Yup. Just at a glance, I don't see even a cursory attempt to prove that the upper bound on the proposed algorithm's time complexity is actually a polynomial. It depends on the "serial numbers of [...] monomials, in the natural order of monomials". But the number of different possible monomials in a polynomial with bounded length is obviously exponential.

The closest the paper gets to actually talking about time complexity is:

> As it is mentioned in [3], there is no sense to make use of the formal definition of Turing machine for this problem. From practical point of view, it is much more useful to show existence of a polynomial-time constructive algorithm for solving it ([2]). Therefore, in the next section we will introduce our own definitions and notations, describing a kind of a formal computer, more practically oriented, but resembling that of a Turing machine.

But the so-called "formal computer" is only described in extremely hand-wavy and informal terms, and no attempt is made to relate the number of "steps" it would perform to the running time of a corresponding Turing machine.