Theoretical Computer Science
cc.complexity-theory alternating-hierarchy polynomial-hierarchy
Updated Thu, 02 Jun 2022 06:06:51 GMT

canonical complete problems for $\Delta^P_n$

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$?


(This is a slightly more detailed version of my earlier comment, in response to the askers 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 k1 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.

Comments (3)

  • +0 – Thank you very much for your answer. For my needs, this is exactly what I have been looking for. — Dec 21, 2010 at 12:18  
  • +0 – @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. — Dec 21, 2010 at 13:01  
  • +0 – @ 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 :). — Dec 21, 2010 at 13:17