<p>My argument is not the most sound one, I would call more of a proof idea. My idea is a variation of Ladner's theorem, where instead of padding we use alternations of quantifers.</p>

<p>All levels of $PH$ have complete problems with a <em>constant</em> number of quantifier alternations. Consider now quantified formulas with at most $f(n)$ alternations where $f(n)\in o(1)\cap \omega(n)$, i.e. a sublinear non-constant function. For every such $f(n)$, let $f(n)-SAT$ be the language of satisfiable quantified formulas with at most $f(n)$ alternations.</p>

<p>It is apparent that $f(n)-SAT$ is in $PSPACE$ as it is a special version of $TQBF$, however I believe it is not in $PH$ and it is not $PSPACE$-complete.</p>

<p>Suppose that for some constant $f(n)$, $f(n)-SAT$ is $PSPACE$-complete. Then by definition,TQBF is Karp-reducible to $f(n)-SAT$. Thus we have a reduction that can limit the number of alterations from at most $n$ to at most $f(n)$. The same reduction, perhaps applied repetitively, could be probably used to reduce $f(n)$ to a constant number of alternations, thus it would be in $PH$. That would lead to a contradiction of the hypothesis that $PH \neq PSPACE$.</p>

<p>Therefore, $f(n)-SAT$ canoot be $PSPACE$-complete and since such a reduction does not exist, neither in $PH$.</p>

<p>One weak point of this idea is that perhaps the reduction can reduce the alternations to a small function, that is however in $o(1)$.</p>

CC BY-SA 3.0
2011-08-07T16:50:44.940Z
I cannot follow your argument completely but it seems to me that you are assuming implicitly that $\mathsf{PH}$ does not collapse and $n^{o(1)}\text{-}QBF$ is not $\mathsf{PSpace\text{-}complete}$ which need not be true. E.g. it is possible that SAT is complete for $\mathsf{PSpace}$.
Kaveh
CC BY-SA 3.0
2011-08-07T15:02:12.833Z
2011-08-07T15:02:12.833Z
chazisop
<p>This is corollary 13 in Uwe Schöning's paper "<a href="http://dx.doi.org/10.1016/0304-3975%2882%2990114-1">A uniform approach to obtain diagonal sets in complexity classes</a>":</p>

<blockquote>
  <h3>Corollary 13:</h3>
  
  <p>If $\mathsf{PSpace} \neq \mathsf{PH}$, then there exist sets in $\mathsf{PSpace}$ which are not $\mathsf{PSpace\text{-}complete}$ w.r.t. $\leq^{\mathsf{P}}_T$ and which are not in the polynomial hierarchy.</p>
  
  <p>Proof:</p>
  
  <p>If $\mathsf{PSpace} \neq \mathsf{PH}$, then QBF is not in the polynomial hierarchy.
  Hence $A_1 = \emptyset$, $A_2 = QBF$, $C_1 = \{\mathsf{NP\text{-}complete} \text{ w.r.t. } \leq^{\mathsf{P}}_T \}$, $C_2 = \mathsf{PH}$, satisfy the hypothesis of the main theorem. </p>
</blockquote>

<hr>

<blockquote>
  <h3>Main theorem:</h3>
  
  <p>Let $A_1$, $A_2$ be recursive sets and $C_1$, $C_2$ be classes of recursive sets with the following properties:</p>
  
  <ol>
  <li>$A_1 \notin C_1$, $A_2 \notin C_2$</li>
  <li>$C_1$ and $C_2$ are recursively presentable, </li>
  <li>$C_1$ and $C_2$ are closed under finite variations. </li>
  </ol>
  
  <p>Then there exists a recursive set $A$ such that:</p>
  
  <ol>
  <li>$A \notin C_1$, $A \notin C_2$, </li>
  <li>if $A_1 \in \mathsf{P}$ and $A_2\notin \{ \emptyset, \Sigma^* \}$, then $A \leq^{\mathsf{P}}_m A_2$. </li>
  </ol>
</blockquote>

<p>(note: I updated the names to current ones)</p>

<hr>

<p>There are two interpretations for monotone QBF:</p>

<ol>
<li><p>QBFs where the quantifier free part is monotone in all variables. Then this is in $\mathsf{P}$ as Ryan noted. Because the quantifier-free part is monotone in quantified variables we can remove the quantifiers and replace the existentially quantified variables with 1 and universally quantified variables with 0, the original quantified formula is true iff this modified quantifier-free formula is true, and this reduces the problem to monotone formula evaluation which is in (and complete for) $\mathsf{NC^1} \subseteq \mathsf{P}$. (If we are taking supremum of a function over a variable and the function is monotone in that variable we only need to compute the value of the function over the maximal values for that variable.)</p></li>
<li><p>QBFs which are monotone in the input variables. This is $\mathsf{PSpace}$ under $\mathsf{AC^0}$ reductions, the reduction of the QBF to this version is simple and is similar to the proof for monotone boolean formula evaluation being complete for $\mathsf{NC^1}$ or monotone circuit value being complete for $\mathsf{P}$.</p></li>
</ol>

CC BY-SA 3.0
2011-08-06T14:28:23.953Z
What's AC$^0$ reduction? If monotone QBF is PSPACE-complete, then QBF is reducible to monotone QBF and that means {AND, OR} is complete, doesn't it?
Zirui Wang
CC BY-SA 3.0
2011-08-06T21:48:19.333Z
@Zirui Wang: If you don't know that is an $\mathsf{AC^0}$ reduction, then I suggest that you read a good complexity textbook like Arora and Barak, and check the proof that monotone circuit value problem is complete for $\mathsf{P}$, these are not research level questions.
Kaveh
CC BY-SA 3.0
2011-08-07T13:49:58.383Z
Can you give more details on your claim that the argument for the existence of NPI "applies in this case"? I think it's an interesting result because (1) the authors of the NPI argument did not mention this connection and (2) Schoning uses a more general argument for both cases so if NPI implies "PSPACEI" then maybe it could imply more and the general argument is not necessary.
Zirui Wang
CC BY-SA 3.0
2011-08-07T21:15:33.780Z
@Kaveh: (1) I did not link to that answer, but this is not a big deal. :)  (2) Theorems 5 and 7 of Ladner _as they are stated_ do not seem to imply the existence of non-PSPACE-complete language outside PH under the assumption PH≠PSPACE (because PH cannot be characterized by either C-time or C-space).  I guess that this is why Schöning explicitly stated this case in the paper.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-09T05:12:54.950Z
@Tsuyoshi: thanks :), I should have been more careful, removed my comment, also made the answer CW.
Kaveh
CC BY-SA 3.0
2013-05-29T17:44:16.093Z
Generalization of Ladner's theorem.
Kaveh
CC BY-SA 3.0
2011-08-06T13:21:21.033Z
2011-08-07T22:23:41.167Z
2011-08-07T22:23:41.167Z
Kaveh
<blockquote>
  <p>Suppose PH is strictly contained in PSPACE. Is there a problem in PSPACE that is not in PH and not PSPACE-complete?</p>
</blockquote>

<p>I encountered a language that is in PSPACE. The question is whether it's in PH. So far I don't have any success in either proving it's in PH or proving it's PSPACE-complete. I wonder if there is a languge that's not in PH and not PSPACE-complete given PH $\ne$ PSPACE.</p>

CC BY-SA 3.0
2011-08-06T11:15:55.727Z
One candidate is what I call monotone QBF. It's like QBF but the NOT gate is not allowed. Is this problem in PH?
Zirui Wang
CC BY-SA 3.0
2011-08-06T15:27:28.057Z
See an [answer](http://cstheory.stackexchange.com/questions/799/generalized-ladners-theorem/863#863) to a related question, and specifically (Corollary 13 of) Schöning’s paper cited there.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-06T16:02:23.343Z
I take "monotone QBF" to mean that the underlying predicate is a monotone circuit over the quantified variables. If I understand what you mean by "monotone QBF", this problem is solvable in polynomial time.
Ryan Williams
CC BY-SA 3.0
2011-08-06T21:49:39.957Z
@Ryan, if your interpretation is what OP had in mind then indeed it is in $\mathsf{P}$ as you wrote.
Kaveh
CC BY-SA 3.0
2011-08-06T21:52:40.017Z
@Tsuyoshi, I forgot about that question. Do you think we should close this question as a duplicate?
Kaveh
CC BY-SA 3.0
2011-08-06T22:00:01.977Z
@Kaveh: I do not know, but probably either way is fine.  I would not mind if it is closed, but it may be worth keeping because (1) it will probably show up when someone search “PSPACE intermediate” on the website, and (2) it contains some information about “monotone QBF” which is completely independent from the other question.  I do not know the details of the recent change about closing (sometimes closing automatically deletes a question), and I am less inclined to close because of that.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-07T07:31:18.167Z
Schoning's result is general, but it doesn't say whether there is an EXP-intermediate language, that is, a language (a) in EXP, (b) not in PSPACE, and (c) not EXP-complete, given PSPACE $\ne$ EXP.
Zirui Wang
CC BY-SA 3.0
2011-08-07T07:54:54.203Z
@Ryan: How do you do it in polynomial time?
Zirui Wang
CC BY-SA 3.0
2011-08-07T17:00:07.507Z
@Zirui: Really?  I would be surprised if Schöning’s result did not apply to the EXP vs PSPACE case.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-07T17:08:23.207Z
@Zirui Wang: it seems to me that you lack understanding of basics in complexity theory, it is better to read a standard textbook in complexity theory before trying to ask these questions here. Please also read the FAQ.
Kaveh
<cc.complexity-theory><complexity-classes><polynomial-hierarchy>
Is there a PSPACE-intermediate language?
Zirui Wang
# Is there a PSPACE-intermediate language?

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

> Suppose PH is strictly contained in PSPACE. Is there a problem in PSPACE that is not in PH and not PSPACE-complete?

I encountered a language that is in PSPACE. The question is whether it's in PH. So far I don't have any success in either proving it's in PH or proving it's PSPACE-complete. I wonder if there is a languge that's not in PH and not PSPACE-complete given PH $\ne$ PSPACE.

**Tags:** cc.complexity-theory, complexity-classes, polynomial-hierarchy

> **Comments:**
> **username_0**: One candidate is what I call monotone QBF. It's like QBF but the NOT gate is not allowed. Is this problem in PH?  
> **username_1**: See an [answer](http://cstheory.stackexchange.com/questions/799/generalized-ladners-theorem/863#863) to a related question, and specifically (Corollary 13 of) Schöning’s paper cited there.  
> **username_2**: I take "monotone QBF" to mean that the underlying predicate is a monotone circuit over the quantified variables. If I understand what you mean by "monotone QBF", this problem is solvable in polynomial time.  
> **username_3**: @Ryan, if your interpretation is what OP had in mind then indeed it is in $\mathsf{P}$ as you wrote.  
> **username_3**: @Tsuyoshi, I forgot about that question. Do you think we should close this question as a duplicate?  
> **username_1**: @username_3: I do not know, but probably either way is fine.  I would not mind if it is closed, but it may be worth keeping because (1) it will probably show up when someone search “PSPACE intermediate” on the website, and (2) it contains some information about “monotone QBF” which is completely independent from the other question.  I do not know the details of the recent change about closing (sometimes closing automatically deletes a question), and I am less inclined to close because of that.  
> **username_0**: Schoning's result is general, but it doesn't say whether there is an EXP-intermediate language, that is, a language (a) in EXP, (b) not in PSPACE, and (c) not EXP-complete, given PSPACE $\ne$ EXP.  
> **username_0**: @Ryan: How do you do it in polynomial time?  
> **username_1**: @Zirui: Really?  I would be surprised if Schöning’s result did not apply to the EXP vs PSPACE case.  
> **username_3**: @username_0: it seems to me that you lack understanding of basics in complexity theory, it is better to read a standard textbook in complexity theory before trying to ask these questions here. Please also read the FAQ.  

---

## 2 answers

### Answer by username_3 on 2011-08-06. Score: 10 | Accepted answer

This is corollary 13 in Uwe Schöning's paper "[A uniform approach to obtain diagonal sets in complexity classes](http://dx.doi.org/10.1016/0304-3975%2882%2990114-1)":

> ### Corollary 13:
>
> If $\mathsf{PSpace} \neq \mathsf{PH}$, then there exist sets in $\mathsf{PSpace}$ which are not $\mathsf{PSpace\text{-}complete}$ w.r.t. $\leq^{\mathsf{P}}\_T$ and which are not in the polynomial hierarchy.
>
> Proof:
>
> If $\mathsf{PSpace} \neq \mathsf{PH}$, then QBF is not in the polynomial hierarchy.
> Hence $A\_1 = \emptyset$, $A\_2 = QBF$, $C\_1 = \{\mathsf{NP\text{-}complete} \text{ w.r.t. } \leq^{\mathsf{P}}\_T \}$, $C\_2 = \mathsf{PH}$, satisfy the hypothesis of the main theorem.

---

> ### Main theorem:
>
> Let $A\_1$, $A\_2$ be recursive sets and $C\_1$, $C\_2$ be classes of recursive sets with the following properties:
>
> 1. $A\_1 \notin C\_1$, $A\_2 \notin C\_2$
> 2. $C\_1$ and $C\_2$ are recursively presentable,
> 3. $C\_1$ and $C\_2$ are closed under finite variations.
>
> Then there exists a recursive set $A$ such that:
>
> 1. $A \notin C\_1$, $A \notin C\_2$,
> 2. if $A\_1 \in \mathsf{P}$ and $A\_2\notin \{ \emptyset, \Sigma^\* \}$, then $A \leq^{\mathsf{P}}\_m A\_2$.

(note: I updated the names to current ones)

---

There are two interpretations for monotone QBF:

1. QBFs where the quantifier free part is monotone in all variables. Then this is in $\mathsf{P}$ as Ryan noted. Because the quantifier-free part is monotone in quantified variables we can remove the quantifiers and replace the existentially quantified variables with 1 and universally quantified variables with 0, the original quantified formula is true iff this modified quantifier-free formula is true, and this reduces the problem to monotone formula evaluation which is in (and complete for) $\mathsf{NC^1} \subseteq \mathsf{P}$. (If we are taking supremum of a function over a variable and the function is monotone in that variable we only need to compute the value of the function over the maximal values for that variable.)
2. QBFs which are monotone in the input variables. This is $\mathsf{PSpace}$ under $\mathsf{AC^0}$ reductions, the reduction of the QBF to this version is simple and is similar to the proof for monotone boolean formula evaluation being complete for $\mathsf{NC^1}$ or monotone circuit value being complete for $\mathsf{P}$.

> **Comments:**
> **username_0**: What's AC$^0$ reduction? If monotone QBF is PSPACE-complete, then QBF is reducible to monotone QBF and that means {AND, OR} is complete, doesn't it?  
> **username_3**: @username_0: If you don't know that is an $\mathsf{AC^0}$ reduction, then I suggest that you read a good complexity textbook like Arora and Barak, and check the proof that monotone circuit value problem is complete for $\mathsf{P}$, these are not research level questions.  
> **username_0**: Can you give more details on your claim that the argument for the existence of NPI "applies in this case"? I think it's an interesting result because (1) the authors of the NPI argument did not mention this connection and (2) Schoning uses a more general argument for both cases so if NPI implies "PSPACEI" then maybe it could imply more and the general argument is not necessary.  
> **username_1**: @username_3: (1) I did not link to that answer, but this is not a big deal. :)  (2) Theorems 5 and 7 of Ladner _as they are stated_ do not seem to imply the existence of non-PSPACE-complete language outside PH under the assumption PH≠PSPACE (because PH cannot be characterized by either C-time or C-space).  I guess that this is why Schöning explicitly stated this case in the paper.  
> **username_3**: @Tsuyoshi: thanks :), I should have been more careful, removed my comment, also made the answer CW.  
> **username_3**: Generalization of Ladner's theorem.  

---

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

My argument is not the most sound one, I would call more of a proof idea. My idea is a variation of Ladner's theorem, where instead of padding we use alternations of quantifers.

All levels of $PH$ have complete problems with a *constant* number of quantifier alternations. Consider now quantified formulas with at most $f(n)$ alternations where $f(n)\in o(1)\cap \omega(n)$, i.e. a sublinear non-constant function. For every such $f(n)$, let $f(n)-SAT$ be the language of satisfiable quantified formulas with at most $f(n)$ alternations.

It is apparent that $f(n)-SAT$ is in $PSPACE$ as it is a special version of $TQBF$, however I believe it is not in $PH$ and it is not $PSPACE$-complete.

Suppose that for some constant $f(n)$, $f(n)-SAT$ is $PSPACE$-complete. Then by definition,TQBF is Karp-reducible to $f(n)-SAT$. Thus we have a reduction that can limit the number of alterations from at most $n$ to at most $f(n)$. The same reduction, perhaps applied repetitively, could be probably used to reduce $f(n)$ to a constant number of alternations, thus it would be in $PH$. That would lead to a contradiction of the hypothesis that $PH \neq PSPACE$.

Therefore, $f(n)-SAT$ canoot be $PSPACE$-complete and since such a reduction does not exist, neither in $PH$.

One weak point of this idea is that perhaps the reduction can reduce the alternations to a small function, that is however in $o(1)$.

> **Comments:**
> **username_3**: I cannot follow your argument completely but it seems to me that you are assuming implicitly that $\mathsf{PH}$ does not collapse and $n^{o(1)}\text{-}QBF$ is not $\mathsf{PSpace\text{-}complete}$ which need not be true. E.g. it is possible that SAT is complete for $\mathsf{PSpace}$.  

---

