[Solved]: Showing that a problem in X is not X-Complete

Problem Detail: 

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.

Asked By : Dave Clarke

Answered By : Ryan Williams

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1002