Let me state the problem again:

Suppose PSPACE $\ne$ EXP. Is there a language in EXP - PSPACE that is not PSPACE-hard?


I have a problem that's in EXP. Currently I don't think it's in PSPACE. Besides proving it's EXP-complete, what else can I do? Since it seem not to be in PSPACE, I start to think it's PSPACE-hard. But is this necessary? That's why I asked this question.

Actually I have a related question, that is, given PSPACE $\ne$ EXP, whether there is a language in EXP - PSPACE that is not EXP-hard. A yes answer to the main question will imply a yes answer to this question. I think answering this question will also help me somehow.

  • $\begingroup$ $PSPACE-hard$ functions include $PSPACE-complete$ languages, that are of course in $PSPACE$. I believe that you mean $PSPACE-hard \backslash PSPACE-complete$? $\endgroup$
    – chazisop
    Aug 7 '11 at 15:05
  • 2
    $\begingroup$ @chazisop: "Since it seem not to be in PSPACE, I start to think it's PSPACE-hard. But is this necessary? That's why I asked this question." $\endgroup$ Aug 7 '11 at 15:19

The proof of Ladner's theorem doesn't use any special properties of P and NP and the same proof unchanged will show, assuming EXP<>PSPACE, there is a language L in EXP-PSPACE and not EXP-complete under either P-time or PSPACE-reductions.

You need the full Landner look-back trick to keep L in EXP.


The answer to your questions depends on what kind of reductions you are using for your notion of hardness. If you are using polynomial-space reductions, then I believe Daniel's answer is correct. If you are using polynomial-time reductions, however, just the opposite is true.

Namely, assuming $EXP \neq PSPACE$, there is a problem in $EXP$ which is neither in $PSPACE$ nor hard for $PSPACE$ under polynomial-time reductions. This can essentially be constructed by diagonalizing against all possible polynomial-time reductions to $QBF$ (preventing the constructed language from being in $PSPACE$) and from $QBF$ (preventing the constructed language from being $PSPACE$-hard).

Also, by the general version of Ladner's Theorem, if $EXP \neq PSPACE$ then there are problems in $EXP \backslash PSPACE$ which are not $EXP$-hard under polynomial-time reductions.

  • $\begingroup$ Oops, deleted my comment because I couldn't edit it. Thanks though, Kaveh :) Also - What I'm thinking of is going to branch into an entirely different direction, so I'll ask a new question later if so $\endgroup$ Aug 7 '11 at 17:19
  • $\begingroup$ @Daniel Apon: :) $\endgroup$
    – Kaveh
    Aug 7 '11 at 17:22
  • $\begingroup$ @Joshua: Why do you consider polynomial-time reduction? I think for PSPACE-hardness, polynomial-space reduction is sufficient. Why do you restrict yourself to polynomial time? $\endgroup$
    – Zirui Wang
    Aug 8 '11 at 1:38
  • 1
    $\begingroup$ @Zirui: under polynomial-space reductions, all problems in PSPACE are PSPACE-complete... If you are only interested in problems "above" PSPACE, then you could use polynomial-space reductions. $\endgroup$ Aug 8 '11 at 15:05

Please see comments.

No to the first question. Assuming that $\mathsf{EXP}$ - $\mathsf{PSPACE}$ is not empty, since $\mathsf{PSPACE} \subseteq \mathsf{EXP}$, all languages in $\mathsf{EXP}$ - $\mathsf{PSPACE}$ are $\mathsf{PSPACE}$-hard.

  • $\begingroup$ And I would believe Yes to the second question as well, for similar reasons as before. $\endgroup$ Aug 7 '11 at 14:44
  • 1
    $\begingroup$ I don't understand this argument. Are you saying that if X and Y are complexity classes such that $X\subseteq Y$ and $X \neq Y$ then everything in Y\X is X-hard? $\endgroup$ Aug 7 '11 at 15:31
  • 1
    $\begingroup$ That was my implication -- Do you have a counterexample in mind? $\endgroup$ Aug 7 '11 at 16:09
  • 10
    $\begingroup$ Example 1: Let's say your implication is true. Let X be NP and Y be PSPACE. If X is not equal to Y this means NP = co-NP (if it's not then a co-NP-complete problem will be NP-hard by your claim and thus NP = co-NP). If X is equal to Y, then NP = PSPACE, and thus NP = co-NP. So we have proved that NP = co-NP without any assumptions. Example 2: Let X = AC0[3] and Y = L. We know PARITY is not in AC0[3], so PARITY must be AC0[3]-hard. But that will put AC0[3] inside AC0[2] (which contains PARITY) contradicting the known fact that AC0[3] is not contained in AC0[2]. $\endgroup$ Aug 7 '11 at 16:42
  • 2
    $\begingroup$ I stand corrected! $\endgroup$ Aug 7 '11 at 16:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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