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

• Here we have LaTeX support, so you may like to edit the question with dollar sign included. This makes it easier to read. – Hsien-Chih Chang 張顯之 Dec 20 '10 at 11:41
• I added in the relevant symbols. – Suresh Venkat Dec 20 '10 at 12:19
• 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. – Tsuyoshi Ito Dec 20 '10 at 13:08
• 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. – Hsien-Chih Chang 張顯之 Dec 21 '10 at 2:25
• This is a nice question! – Huck Bennett Dec 21 '10 at 4:11

## 1 Answer

(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.

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