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$ Dec 20 '10 at 11:41
  • 3
    $\begingroup$ I added in the relevant symbols. $\endgroup$ Dec 20 '10 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$ Dec 20 '10 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$ Dec 21 '10 at 2:25
  • $\begingroup$ This is a nice question! $\endgroup$ Dec 21 '10 at 4:11

(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
    Dec 21 '10 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$ Dec 21 '10 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
    Dec 21 '10 at 13:17

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.