8
$\begingroup$

Background: It is possible (see e.g., this) 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.

Improve this question
$\endgroup$

4 Answers 4

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Ah, perhaps this is why Blum-Cucker-Shub-Smale didn't mention $\mathrm{PSPACE}$. Thanks for the answer. Incidentally, why is "is the given number an integer?" solvable in constant space? $\endgroup$
    – Akhil Mathew
    Commented Apr 16, 2010 at 19:33
  • $\begingroup$ Just sum up ones until the sum gets greater than the modulus of the number. I'm assuming the machine has the constants 0 and 1 built-in (if not, modify the problem so that they are given as part of input). $\endgroup$
    – Sergei Ivanov
    Commented Apr 16, 2010 at 20:01
  • $\begingroup$ Oh right. That makes sense. $\endgroup$
    – Akhil Mathew
    Commented Apr 16, 2010 at 23:34
  • $\begingroup$ relating to the problem of collapsing into single numbers, it's well known that we can collapse P and NP (and even P and PSPACE) if we're allowed merely do floor function computations in constant time - the idea is similar to what Sergei proposes. $\endgroup$
    – Suresh Venkat
    Commented Apr 18, 2010 at 6:07
  • $\begingroup$ @SureshVenkat If we can do floor operations in Linear Programming would that give $P=PSPACE$? $\endgroup$
    – Turbo
    Commented Jul 21, 2018 at 5:08
6
$\begingroup$

First, it seems clear that there are at least some rings with your property, since the case of $Z_3$ or any other finite ring corresponds to simply having a larger finite alphabet, which would amount to the classical case. The difficulty would seem to come in only for infinite rings, right?

Let me also mention that there is an article by Mihai Prunescu explaining that P is not NP for all infinite abelian groups; but this computational model appears not to be exactly what you had in mind.

There is apparantly also another kind of computational algebraization than the one you mention. Scott Aaronson at MIT has slides for a talk that explain how many of the complexity results algebraize in a sense he explains (which appears to be different from the sense of the question). In particular, he claims in the abstract of this talk posted on his blog that the IP = PSPACE result does algebraize.

Abstract

Algebrization: A New Barrier in Complexity Theory

Any proof of P≠NP will have to overcome two barriers: relativization and natural proofs. Yet over the last decade, we have seen circuit lower bounds (for example, that PP does not have linear-size circuits) that overcome both barriers simultaneously. So the question arises of whether there is a third barrier to progress on the central questions in complexity theory.

In this talk we present such a barrier, which we call “algebraic relativization” or “algebrization.” The idea is that, when we relativize some complexity class inclusion, we should give the simulating machine access not only to an oracle A, but also to the low-degree extension of A over a finite field or ring.

We systematically go through basic results and open problems in complexity theory to delineate the power of the new algebrization barrier. We first show that all known non-relativizing results — both inclusions such as IP=PSPACE and MIP=NEXP, and separations such as MAEXP⊄P/poly — do indeed algebrize. We next show that most open problems — including P versus NP, P versus BPP, and NEXP versus P/poly — will require non-algebrizing techniques, of which we currently have not a single example. In some cases algebrization seems to explain exactly why progress stopped where it did: for example, why we have superlinear circuit lower bounds for PromiseMA but not for NP.

We also exhibit a surprising connection between algebrization and communication complexity. Using this connection, we give an MA-protocol for the Inner Product function with O(√n log(n)) communication (essentially matching a lower bound of Klauck), and describe a pure communication complexity conjecture whose truth would imply P≠NP.

However, his sense of using the ring is rather different from the sense you used in your question, since he seems to be using a classical oracle Turing machine with additional features, and so I am unsure to what extent his concept settles the question in your sense. (And I think he should spell it as "algebraize", just as we write algebraic.)

Improve this answer
$\endgroup$
0
2
$\begingroup$

A related example is Toda's theorem, which can be shown to hold over the reals and now over the complex numbers.

Improve this answer
$\endgroup$
2
$\begingroup$

This does not directly answer your question, but it is related to issues of relativizing IP and PSPACE.

For a random oracle A, IPA ≠ PSPACEA with probability 1.

The problems coincide relative to a random oracle with probability either 0 or 1 by Komolgorov's zero-one law. That they are distinct for almost all oracles was proved by Chang-Chor-Goldreich-Hartmanis-Håstad-Ranjan-Rohatgi in "The random oracle hypothesis is false." J. Comput. System Sci. 49 (1994), no. 1, 24–39. Note however that if you pass from IP to IPP, where the error probability is only ≤ 1/2, you do have that IPPA = PSPACEA for a random oracle A, so these are subtle issues.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks! I have heard something like that for P and NP. What is the definition of a random oracle though? $\endgroup$
    – Akhil Mathew
    Commented Apr 16, 2010 at 19:35
  • 1
    $\begingroup$ @Akhil: The short answer is that the events $a\in A$ are independently uniformly distributed for all strings $a$. The longer answer is that you identify oracles with their characteristic functions, i.e., elements of $\{0,1\}^{\Sigma^*}$. This set carries the product topology (homeomorphic to the Cantor set), and you take the completion of the product probability measure on its Borel subsets, where $\{0,1\}$ is given the uniform probability measure. That is, for pairwise distinct $a_1,\dots,a_n,b_1,\dots,b_m$, $\Pr_A(a_1\in A,\dots,a_n\in A,b_1\notin A,\dots,b_m\notin A)=2^{-(n+m)}$. $\endgroup$
    – Emil Jeřábek
    Commented Sep 5, 2011 at 16:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .