3
$\begingroup$

Let me state the problem again:

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

Context

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.

Improve this question
$\endgroup$
2
  • $\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
    Commented Aug 7, 2011 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$
    – Daniel Apon
    Commented Aug 7, 2011 at 15:19

3 Answers 3

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
7
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\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$
    – Daniel Apon
    Commented Aug 7, 2011 at 17:19
  • $\begingroup$ @Daniel Apon: :) $\endgroup$
    – Kaveh
    Commented Aug 7, 2011 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
    Commented Aug 8, 2011 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$
    – Joshua Grochow
    Commented Aug 8, 2011 at 15:05
0
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ And I would believe Yes to the second question as well, for similar reasons as before. $\endgroup$
    – Daniel Apon
    Commented Aug 7, 2011 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$
    – Robin Kothari
    Commented Aug 7, 2011 at 15:31
  • 1
    $\begingroup$ That was my implication -- Do you have a counterexample in mind? $\endgroup$
    – Daniel Apon
    Commented Aug 7, 2011 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$
    – Robin Kothari
    Commented Aug 7, 2011 at 16:42
  • 2
    $\begingroup$ I stand corrected! $\endgroup$
    – Daniel Apon
    Commented Aug 7, 2011 at 16:53

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.