6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ One candidate is what I call monotone QBF. It's like QBF but the NOT gate is not allowed. Is this problem in PH? $\endgroup$ – Zirui Wang Aug 6 '11 at 11:15
  • 3
    $\begingroup$ See an answer to a related question, and specifically (Corollary 13 of) Schöning’s paper cited there. $\endgroup$ – Tsuyoshi Ito Aug 6 '11 at 15:27
  • 1
    $\begingroup$ 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. $\endgroup$ – Ryan Williams Aug 6 '11 at 16:02
  • 1
    $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Aug 6 '11 at 22:00
  • 2
    $\begingroup$ @Zirui: Really? I would be surprised if Schöning’s result did not apply to the EXP vs PSPACE case. $\endgroup$ – Tsuyoshi Ito Aug 7 '11 at 17:00
10
$\begingroup$

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:

  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}$.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Zirui Wang Aug 6 '11 at 14:28
  • 3
    $\begingroup$ @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. $\endgroup$ – Kaveh Aug 6 '11 at 21:48
  • $\begingroup$ 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. $\endgroup$ – Zirui Wang Aug 7 '11 at 13:49
  • 1
    $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Aug 7 '11 at 21:15
  • $\begingroup$ @Tsuyoshi: thanks :), I should have been more careful, removed my comment, also made the answer CW. $\endgroup$ – Kaveh Aug 9 '11 at 5:12
0
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ 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}$. $\endgroup$ – Kaveh Aug 7 '11 at 16:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.