Showing that a problem in X is not X-Complete

Question

The Existential Theory of the Reals is in PSPACE, but I don't know whether it is PSPACE-Complete. If I believe that it is not the case, how could I prove it?

More generally, given a problem in some complexity class X, how can I show that it is not X-Complete? For example, X could be NP, PSPACE, EXPTIME.

Answer 1

Actually proving $X$ is not $PSPACE$-complete (under, say, polynomial-time reductions) would be extremely hard to do.

If $P=PSPACE$, then all non-trivial (i.e., not $\varnothing$ and not $\Sigma^{\star}$) and infinite problems in $PSPACE$ are $PSPACE$-complete under polynomial-time reductions. Since the existential theory of the reals has this non-trivial and infinite property, proving that it isn't $PSPACE$-complete would imply $P \neq PSPACE$. (See the answer to this question on CSTheory.SE for a sketch of the proof.)

Answer 2

A problem in $X$ is not $X$-complete if there are any other problems in $X$ which cannot be reduced to it. One straightforward (but possibly only effective on trivial examples) method would be proving your problem is also in some other complexity class $Y$ such that $Y \subset X$.

For example, if you want to show that your problem is not $EXPTIME$ complete, then it is sufficient to show that it is in $P$, since $P \subsetneq EXPTIME$. However, if you wanted to show that a problem is not $NP$-complete, then it is not necessarily sufficient to show that it is in $P$, since it is not known whether or not $P = NP$.

Answer 3

Look at the accepted answer for this question on MathOverflow, What techniques exist to show that a problem is not NP-complete?. It answers the case when X=NP.

Answer 4

As Ryan wrote, proving that a problem is not hard is not easy.

Let $Q$ be a problem in a complexity class $X$ and $S$ is closed w.r.t. $\leq$ reductions. Proving that $Q$ is not $X$-hard w.r.t. $\leq$ is equivalent to separating the complexity class obtained by taking closure of $Q$ w.r.t. $\leq$. Now, if $Q$ is hard for another class $Y$ w.r.t. $\leq$, then it means separating $Y$ from $X$. As you know, there aren't many separation results.

In your case, $X = \mathsf{PSpace}$, $\leq = \leq^\mathsf{P}_m$, and $Y=\mathsf{P}$.

Because we can't prove such results at the moment (with the possible exception of Ryan :), in place of proving that $Q$ is not $X$-hard, we show that it is in a complexity class that is believed to be smaller than $X$. For example, if you show that $\mathrm{Th}_\exists(\mathbb{R,+,\times,0,1})$ is in $\mathsf{PH}$, then it will be taken as a strong evidence for $Q$ not being $X$-hard. (In logicians' language, if you can't prove an unconditional result, try proving a conditional one assuming a hard to prove but widely believed statement like $\mathsf{P}\neq\mathsf{PSpace}$).