3
$\begingroup$

The complexity class DP can be defined as the set of all languages that are the intersection of an NP language with a coNP language.

I have a language for which I wish to determine the exact complexity class. I know that the language is:

  • It is $\Sigma_2^P$-hard
  • It is $\Pi_2^P$-hard
  • It can be represented as the intersection of a $\Sigma_2^P$ and a $\Pi_2^P$ languages.

Here $\Sigma_2^P$ and $\Pi_2^P$ are the second-level classes in the polynomial hierarchy.

It seems that what I know about my language indicates that it is complete in a complexity class which is analogous to DP, but where DP corresponds to the first level of PH, my class corresponds to the second level.

My questions:

  1. Am I correct in deducing the completeness of my language? It seems plausible but I can't find a proof.
  2. What is the usual name of "my" complexity class? Where has it been studied so far? Is it interesting? Are there known (non-artificial) complete problems for it?

Thanks.

$\endgroup$
  • $\begingroup$ a canonical way to construct complete problems for this kind of class: fix a $\Sigma_2^P$ complete language $L_1$ and a $\Pi_2^P$-complete language $L_2$ and define $L = L_1 \times L_2$. $\endgroup$ – Sasho Nikolov Jun 27 '13 at 2:03
  • $\begingroup$ Yes, but this produces "artifical" problems (in the sense that they have not emerged from elsewhere), and it doesn't help me to prove that my language is hard. $\endgroup$ – Gadi A Jun 27 '13 at 6:04
2
$\begingroup$

The definition of the class that you are referring to is interesting.

Originally, the definition of the class $D^P$, as the class of the languages that are the intersection of an $NP$ language and a co-$NP$ language, appeared in [1]. Then, the idea behind $D^P$ was generalized to the Boolean Hierarchy ($BH$) [2], which is a hierarchy between $NP$ and $\Delta^P_2$, and $D^P$ is at the second level of $BH$, i.e, $D^P = BH(2)$. The definition of $BH$ was subsequently extended to the "Boolean Hierarchy over $\Sigma^P_2$" ($BH_3$) [3], which is a hierarchy similar to $BH$ but located between $\Sigma^P_2$ and $\Delta^P_3$. In $BH_3$, at the second level, there is the class that you are mentioning. Hence, in the literature, this class is sometimes denoted by $BH_3(2)$. However, for the similarity between the definitions of $BH_3(2)$ and $BH(2) = D^P$, pretty soon, in the literature, the notation $D^P_k$ was used to denote the generalization of $D^P$ to upper levels in the polynomial hierarchy, even before a formal definition of it was given. Therefore, the class you are referring to is usally denoted by $D^P_2$.

Regarding the $D^P_k$-hardness of languages, similarly to other definitions, a language $L$ is $D^P_k$-hard if, for every language $L'\in D^P_k$, there is a polynomial reduction from $L'$ to $L$. Unfortunately, showing that a language $L$ is $\Sigma^P_k$-hard and $\Pi^P_k$-hard is not enough to show that $L$ is $D^P_k$-hard. However, if there is a reduction from a $D^P_k$-hard language $L'$ to $L$, then $L$ is $D^P_k$-hard as well. In this respect, it is helpful what it is said in a comment to the initial question. In fact, a problem $L$ can be shown to be hard for $D^P_k$ if there is a polynomial reduction to $L$ from the task of recognizing pairs of "yes"-instances of two languages, one $\Sigma^P_k$-hard and the other $\Pi^P_k$-hard. More formally, given two languages $L_1$ and $L_2$, which are $\Sigma^P_k$-hard and $\Pi^P_k$-hard, respectively, if there is a polynomial reduction $h$ such that $\langle s_1,s_2\rangle\in L_1\times L_2 \Leftrightarrow h(\langle s_1,s_2\rangle)\in L$, then $L$ is $D^P_k$-hard [4, by a generalization of the argument in the proof of Theorem 17.1].

[1] C. H. Papadimitriou and M. Yannakakis. The complexity of facets (and some facets of complexity). Journal of Computer and System Sciences, 28(2):244–259, 1984. DOI: 10.1016/0022-0000(84)90068-0

[2] J.-Y. Cai, T. Gundermann, J. Hartmanis, L. A. Hemachandra, V. Sewelson, K. W. Wagner, and G. Wechsung. The boolean hierarchy I: Structural properties. SIAM Journal on Computing, 17(6):1232–1252, 1988. DOI: 10.1137/0217078.

[3] R. Chang and J. Kadin. The boolean hierarchy and the polynomial hierarchy: A closer connection. SIAM Journal on Computing, 25(2):340–354, 1996. DOI: S0097539790178069.

[4] C. H. Papadimitriou. Computational Complexity. Addison Wesley, Reading, MA, USA, 1994.

$\endgroup$
2
$\begingroup$

2) The class can be described as the relativization of DP with an NP oracle, hence I would call it $\mathrm{DP^{NP}}$. While other notations exist in the literature as explained in not-A-or-B’s answer, I do not find them very helpful, as I would have no idea what levels exactly of the hierarchies the various indices denote without looking it up.

1) Your argument is incomplete. A useful criterion is that a language $L\in\mathrm{DP^{NP}}$ is $\mathrm{DP^{NP}}$-complete if and only if it is $\Sigma^P_2$-hard, $\Pi^P_2$-hard, and AND-reducible: the latter means that there is a poly-time function $f$ such that $$f(x,y)\in L\iff x\in L\text{ and }y\in L.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.