# Given PSPACE $\ne$ EXP, is there a non-PSPACE-hard language in EXP - PSPACE?

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.

• $PSPACE-hard$ functions include $PSPACE-complete$ languages, that are of course in $PSPACE$. I believe that you mean $PSPACE-hard \backslash PSPACE-complete$? – chazisop Aug 7 '11 at 15:05
• @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." – Daniel Apon 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.

• 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 – Daniel Apon Aug 7 '11 at 17:19
• @Daniel Apon: :) – Kaveh Aug 7 '11 at 17:22
• @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? – Zirui Wang Aug 8 '11 at 1:38
• @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. – Joshua Grochow Aug 8 '11 at 15:05

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.
• 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? – Robin Kothari Aug 7 '11 at 15:31