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$?
$\begingroup$
$\endgroup$
6
-
2$\begingroup$ Here we have LaTeX support, so you may like to edit the question with dollar sign included. This makes it easier to read. $\endgroup$ – Hsien-Chih Chang 張顯之 Dec 20 '10 at 11:41
-
3$\begingroup$ I added in the relevant symbols. $\endgroup$ – Suresh Venkat Dec 20 '10 at 12:19
-
5$\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Dec 20 '10 at 13:08
-
$\begingroup$ 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. $\endgroup$ – Hsien-Chih Chang 張顯之 Dec 21 '10 at 2:25
-
$\begingroup$ This is a nice question! $\endgroup$ – Huck Bennett Dec 21 '10 at 4:11
|
Show 1 more comment
$\begingroup$
$\endgroup$
3
(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 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.
answered Dec 21 '10 at 12:12
-
$\begingroup$ Thank you very much for your answer. For my needs, this is exactly what I have been looking for. $\endgroup$ – kvaruni Dec 21 '10 at 12:18
-
$\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Dec 21 '10 at 13:01
-
$\begingroup$ @ 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 :). $\endgroup$ – kvaruni Dec 21 '10 at 13:17
