Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Sure It's not easy and no one can provide an answer for your general part :-) I have too many problems I know they are NP but I don't know they are NP-Complete or not (neither too many other people). – user742 Apr 3 '12 at 1:10
up vote 16 down vote accepted

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

share|cite|improve this answer
Certainly looks like I bit off more than I can chew, so to speak. – Dave Clarke Apr 18 '12 at 0:36

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

share|cite|improve this answer

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.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.