<p>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&lt;>PSPACE, there is a language L in EXP-PSPACE and not EXP-complete under either P-time or PSPACE-reductions.</p>

<p>You need the full Landner look-back trick to keep L in EXP. </p>

CC BY-SA 3.0
2011-08-07T22:04:36.617Z
2011-08-07T22:04:36.617Z
Lance Fortnow
<p>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.</p>

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

<p>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.</p>

CC BY-SA 3.0
2011-08-07T17:19:36.117Z
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
CC BY-SA 3.0
2011-08-07T17:22:07.860Z
@Daniel Apon: :)
Kaveh
CC BY-SA 3.0
2011-08-08T01:38:22.273Z
@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
CC BY-SA 3.0
2011-08-08T15:05:43.460Z
@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
CC BY-SA 3.0
2011-08-07T16:42:06.710Z
2011-08-07T16:42:06.710Z
Joshua Grochow
<p>Please see comments.</p>

<hr>

<p>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.</p>

CC BY-SA 3.0
2011-08-07T14:44:43.043Z
And I would believe Yes to the second question as well, for similar reasons as before.
Daniel Apon
CC BY-SA 3.0
2011-08-07T15:31:49.937Z
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
CC BY-SA 3.0
2011-08-07T16:09:47.947Z
That was my implication -- Do you have a counterexample in mind?
Daniel Apon
CC BY-SA 3.0
2011-08-07T16:42:02.577Z
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].
Robin Kothari
CC BY-SA 3.0
2011-08-07T16:53:41.917Z
I stand corrected!
Daniel Apon
CC BY-SA 3.0
2011-08-07T17:27:41.023Z
nice examples by Robin. Note that there is no restriction on how large the larger class can be, so as long as there is a problem outside the smaller class that is not complete for it we can give examples similar to Robin's.
Kaveh
CC BY-SA 4.0
2021-09-05T06:49:08.093Z
Let X=RE and Y=All, The domino problem for Wang tiles is Co-RE complete and therefore outside RE, but it is not RE-hard, as that would mean RE would be a subset of Co-RE/
blademan9999
CC BY-SA 3.0
2011-08-07T14:38:37.793Z
2011-08-07T17:23:20.147Z
2011-08-07T17:23:20.147Z
Daniel Apon
<p>Let me state the problem again:</p>

<blockquote>
  <p>Suppose PSPACE $\ne$ EXP. Is there a language in EXP - PSPACE that is not PSPACE-hard?</p>
</blockquote>

<p><strong>Context</strong></p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-08-07T15:05:16.277Z
$PSPACE-hard$ functions include $PSPACE-complete$ languages, that are of course in $PSPACE$. I believe that you mean $PSPACE-hard \backslash PSPACE-complete$?
chazisop
CC BY-SA 3.0
2011-08-07T15:19:48.323Z
@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
<cc.complexity-theory><complexity-classes>
Given PSPACE $\ne$ EXP, is there a non-PSPACE-hard language in EXP - PSPACE?
Zirui Wang
# Given PSPACE $\ne$ EXP, is there a non-PSPACE-hard language in EXP - PSPACE?

(Asked by: username_0 on 2011-08-07)

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.

**Tags:** cc.complexity-theory, complexity-classes
> **Comments:**
> **username_1**: $PSPACE-hard$ functions include $PSPACE-complete$ languages, that are of course in $PSPACE$. I believe that you mean $PSPACE-hard \backslash PSPACE-complete$?  
> **username_2**: @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."  

---

## 3 answers

### Answer by username_3 on 2011-08-07. Score: 10

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.


---

### Answer by username_4 on 2011-08-07. Score: 7

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.

> **Comments:**
> **username_2**: 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  
> **username_5**: @Daniel Apon: :)  
> **username_0**: @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?  
> **username_4**: @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.  

---

### Answer by username_2 on 2011-08-07. Score: 0

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.

> **Comments:**
> **username_2**: And I would believe Yes to the second question as well, for similar reasons as before.  
> **username_6**: 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?  
> **username_2**: That was my implication -- Do you have a counterexample in mind?  
> **username_6**: 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].  
> **username_2**: I stand corrected!  
> **username_5**: nice examples by Robin. Note that there is no restriction on how large the larger class can be, so as long as there is a problem outside the smaller class that is not complete for it we can give examples similar to Robin's.  
> **username_7**: Let X=RE and Y=All, The domino problem for Wang tiles is Co-RE complete and therefore outside RE, but it is not RE-hard, as that would mean RE would be a subset of Co-RE/  

---

