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

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 *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 1^{t}, 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 1^{n}.)

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.

- +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