<p>The definition of the class that you are referring to is interesting.</p>

<p>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$.</p>

<p>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].</p>

<p>[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</p>

<p>[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.</p>

<p>[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.</p>

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

CC BY-SA 3.0
2017-08-10T09:53:47.423Z
2017-08-10T09:53:47.423Z
not A or B
<p>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.</p>

<p>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.$$</p>

CC BY-SA 3.0
2017-08-10T10:41:41.827Z
2017-08-10T10:41:41.827Z
Emil Jeřábek
<p>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.</p>

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

<ul>
<li>It is $\Sigma_2^P$-hard</li>
<li>It is $\Pi_2^P$-hard</li>
<li>It can be represented as the intersection of a $\Sigma_2^P$ and a $\Pi_2^P$ languages.</li>
</ul>

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

<p>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.</p>

<p>My questions:</p>

<ol>
<li>Am I correct in deducing the completeness of my language? It seems plausible but I can't find a proof.</li>
<li>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?</li>
</ol>

<p>Thanks.</p>

CC BY-SA 3.0
2013-06-27T02:03:57.107Z
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$.
Sasho Nikolov
CC BY-SA 3.0
2013-06-27T06:04:07.903Z
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.
Gadi A
<complexity-classes><polynomial-hierarchy>
An analog of DP for the second level of the polynomial hierarchy
Gadi A
# An analog of DP for the second level of the polynomial hierarchy

(Asked by: username_0 on 2013-06-26)

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.

**Tags:** complexity-classes, polynomial-hierarchy
> **Comments:**
> **username_1**: 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$.  
> **username_0**: 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.  

---

## 2 answers

### Answer by username_2 on 2017-08-10. Score: 7

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.


---

### Answer by username_3 on 2017-08-10. Score: 5

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


---

