canonical complete problems 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 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.

Solved by user60537 (3 )
Dec 21, 2010 at 12:12