**Background:** It is possible (see e.g., [this](http://www.cs.cmu.edu/%7Elblum/PAPERS/TuringMeetsNewton.pdf)) to define a Turing machine over an arbitrary ring. It reduces to the classical notion when the ring is $\mathbb{Z}\_2$; the key difference is that elementary algebraic computations are allowed to be performed in one step (and one has infinite precision). It is possible to define analogs of classical complexity classes (e.g. $\mathrm{P}\_R, \mathrm{NP}\_R, \mathrm{BPP}\_R$, etc. with respect to a ring $R$). Sometimes the ring may be required to be ordered, and the machine is allowed to test for ordering (it is always allowed to test for equality).


It should, therefore, be possible to define a class $\mathrm{IP}\_R$ of problems that can be solved by a polynomial-time interactive proof system over $R$ with error probability $\leq \frac{1}{3}$, a class $\mathrm{PSPACE}\_R$ of problems that can be solved in polynomial space by a (deterministic) Turing machine. (Probably this has already been done, but I just haven't been able to find it.) When $R = \mathbb{Z}\_2$ (i.e. the classical case), it is a known result that $\mathrm{IP}=\mathrm{PSPACE}$.


**Question:** Does the same work over other rings $R$?


Perhaps there might be a problem, since the only proof I've seen (e.g. in Sipser's *Introduction to the Theory of Computation*) uses the $\mathrm{PSPACE}$-completeness of $TQBF$, and I don't know whether that would work over an arbitrary ring.



Does IP = PSPACE work over other rings?
I think PSPACE does not make much sense over arbitrary rings (it is better to consider classes such as PAR).


Consider $R=\mathbb Z$ or $R=\mathbb Q$ with order. You can encode any finite collection of numbers in a single number and extract elements back in constant space. So you can emulate a potentially infinite memory in constant space (or linear, if you count the size of input). So anything decidable at all is in $PSPACE\_R$.


What $IP\_R$ is depends on what kind of probablity distributions the verifier is allowed to use. In any case, I cannot imagine that problems like "is the given number a power of two?" (with input of size 1!) can be solved by IP in constant time.


In the classic Blum-Shub-Smale case (that is, $\mathbb R$ with order), I suggest the problem "is the given number an integer?". It is trivially solvable in constant space and I'm sure it is not in (constant time) IP due to its infinutely many connected components.


