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

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

## Solution

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