Finding whether or not a QBF can be satisfied is a canonical complete problem for both $\Sigma^P_n$ (start from $\exists$) and $\Pi^P_n$ (start from $\forall$). What is the canonical complete problem for $\Delta^P_n$?

  • 2
    $\begingroup$ Here we have LaTeX support, so you may like to edit the question with dollar sign included. This makes it easier to read. $\endgroup$ Commented Dec 20, 2010 at 11:41
  • 3
    $\begingroup$ I added in the relevant symbols. $\endgroup$ Commented Dec 20, 2010 at 12:19
  • 5
    $\begingroup$ The following problem is complete for Δ_k P for obvious reasons: given a Turing machine M with the Σ_{k−1}-SAT oracle and a tally string 1^n, decide whether M accepts the empty input in time at most n. Although I would call this problem a canonical complete problem for Δ_k P, I guess that you are looking for more natural problems. $\endgroup$ Commented Dec 20, 2010 at 13:08
  • $\begingroup$ There's a partial result when n = 2, which is the class $\mathsf{P^{NP}}$. This class has been discussed in MO, and the answer by Ryan O'Donnell is nice. $\endgroup$ Commented Dec 21, 2010 at 2:25
  • $\begingroup$ This is a nice question! $\endgroup$ Commented Dec 21, 2010 at 4:11

1 Answer 1


(This is a slightly more detailed version of my earlier comment, in response to the asker’s request by email.)

Since $\Delta_k^{\rm P} = {\rm P}^{\Sigma_{k-1}^{\rm P}}$ by definition, it should be clear that the following problem is $\Delta_k^{\rm P}$-complete: fix some $\Sigma_{k-1}^{\rm P}$-complete problem L. (For example, L can be the special case of QBF where there are k−1 groups of consecutive quantifiers of the same kind and the first quantifier is existential (∃).) Then given a Turing machine M with the L oracle, a string x and a tally string 1t, decide whether M accepts the input x in time at most t. (A tally string simply means a string on the unary alphabet, that is, a string of the form 1n.)

I would not mind calling this problem a “canonical” $\Delta_k^{\rm P}$-complete problem, but this may not be what you are looking for.

In my earlier comment, I removed the input string x and assumed it was always the empty string. This variant is also $\Delta_k^{\rm P}$-complete because you can hardwire the input string into a Turing machine.

  • $\begingroup$ Thank you very much for your answer. For my needs, this is exactly what I have been looking for. $\endgroup$
    – kvaruni
    Commented Dec 21, 2010 at 12:18
  • $\begingroup$ @kvaruni: You are welcome. By the way, you could post your request as a reply to my comment (by including “@Tsuyoshi” in a comment) instead of sending an email. You can find a (too) detailed explanation of the reply feature on Meta Stack Overflow. $\endgroup$ Commented Dec 21, 2010 at 13:01
  • $\begingroup$ @ Tsuyoshi Thanks for the help. This is my first question and first time ever that I have used this site, so bear with my. I am getting the hang of it :). $\endgroup$
    – kvaruni
    Commented Dec 21, 2010 at 13:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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