canonical complete problems for $\Delta^P_n$

Question

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

Answer 1

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

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.