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.
This is corollary 13 in Uwe Schöning's paper "A uniform approach to obtain diagonal sets in complexity classes":
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:
- $A_1 \notin C_1$, $A_2 \notin C_2$
- $C_1$ and $C_2$ are recursively presentable,
- $C_1$ and $C_2$ are closed under finite variations.
Then there exists a recursive set $A$ such that:
- $A \notin C_1$, $A \notin C_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:
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.)
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}$.
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)$.
