<p>(This is a slightly more detailed version of my earlier comment, in response to the asker’s request by email.)</p>
<p>Since <span class="math-container">$\Delta_k^{\rm P} = {\rm P}^{\Sigma_{k-1}^{\rm P}}$</span> by definition, it should be clear that the following problem is <span class="math-container">$\Delta_k^{\rm P}$</span>-complete: fix some <span class="math-container">$\Sigma_{k-1}^{\rm P}$</span>-complete problem <i>L</i>.  (For example, <i>L</i> can be the special case of QBF where there are <i>k</i>−1 groups of consecutive quantifiers of the same kind and the first quantifier is existential (∃).)  Then given a Turing machine <i>M</i> with the <i>L</i> oracle, a string <i>x</i> and a tally string 1<sup><i>t</i></sup>, decide whether <i>M</i> accepts the input <i>x</i> in time at most <i>t</i>.  (A <em>tally string</em> simply means a string on the unary alphabet, that is, a string of the form 1<sup><i>n</i></sup>.)</p>
<p>I would not mind calling this problem a “canonical” <span class="math-container">$\Delta_k^{\rm P}$</span>-complete problem, but this may not be what you are looking for.</p>
<p>In my earlier comment, I removed the input string <i>x</i> and assumed it was always the empty string.  This variant is also <span class="math-container">$\Delta_k^{\rm P}$</span>-complete because you can hardwire the input string into a Turing machine.</p>

CC BY-SA 2.5
2010-12-21T12:18:52.080Z
Thank you very much for your answer. For my needs, this is exactly what I have been looking for.
kvaruni
CC BY-SA 2.5
2010-12-21T13:01:14.987Z
@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](http://meta.stackexchange.com/questions/43019/how-do-comment-replies-work/43020#43020).
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-21T13:17:30.157Z
@ 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
CC BY-SA 4.0
2010-12-21T12:12:47.443Z
2021-01-18T09:58:22.157Z
2021-01-18T09:58:22.157Z
Tsuyoshi Ito
<p>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$?</p>

CC BY-SA 2.5
2010-12-20T11:41:40.633Z
Here we have [LaTeX support](http://meta.cstheory.stackexchange.com/questions/3/latex-math-support), so you may like to edit the question with dollar sign included. This makes it easier to read.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-20T12:19:10.833Z
I added in the relevant symbols.
Suresh Venkat
CC BY-SA 2.5
2010-12-20T13:08:36.927Z
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
CC BY-SA 2.5
2010-12-21T02:25:24.590Z
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](http://mathoverflow.net/questions/2218/characterize-pnp/2240#2240) is nice.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-21T04:11:47.940Z
This is a nice question!
Huck Bennett
CC BY-SA 2.5
2010-12-21T09:12:55.583Z
Thanks to Suresh Venkat and Hsien-Chich Chang 張顯之, I did not know that there was support for LaTeX. Very nice feature, indeed.
kvaruni
<cc.complexity-theory><alternating-hierarchy><polynomial-hierarchy>
canonical complete problems for $\Delta^P_n$
kvaruni
# canonical complete problems for $\Delta^P_n$

(Asked by: username_0 on 2010-12-20)

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

**Tags:** cc.complexity-theory, alternating-hierarchy, polynomial-hierarchy

> **Comments:**
> **username_1**: Here we have [LaTeX support](http://meta.cstheory.stackexchange.com/questions/3/latex-math-support), so you may like to edit the question with dollar sign included. This makes it easier to read.  
> **username_2**: I added in the relevant symbols.  
> **username_3**: 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.  
> **username_1**: 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](http://mathoverflow.net/questions/2218/characterize-pnp/2240#2240) is nice.  
> **username_4**: This is a nice question!  
> **username_0**: Thanks to username_2 and Hsien-Chich Chang 張顯之, I did not know that there was support for LaTeX. Very nice feature, indeed.  

---

## 1 answers

### Answer by username_3 on 2010-12-21. Score: 5 | Accepted 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 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*n*.)

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.

> **Comments:**
> **username_0**: Thank you very much for your answer. For my needs, this is exactly what I have been looking for.  
> **username_3**: @username_0: 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](http://meta.stackexchange.com/questions/43019/how-do-comment-replies-work/43020#43020).  
> **username_0**: @ 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 :).  

---

