# 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