18
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$
    – user742
    Commented Apr 3, 2012 at 1:10

4 Answers 4

16
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Certainly looks like I bit off more than I can chew, so to speak. $\endgroup$ Commented Apr 18, 2012 at 0:36
11
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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