Complexity Class $\mathsf{DP}$

The decision problems $L = L_1 \cap L_2$ with $L_1 \in \mathsf{NP}$ and $L_2 \in \mathsf{coNP}$ , i.e. the intersection of a problem in $\mathsf{NP}$ and a problem in $\mathsf{coNP}$ .

Reference

Papadimitriou, C.H. & Yannakakis, M. (1984). The Complexity of Facets (and Some Facets of Complexity). Journal of Computer and System Sciences, 28(2), pp. 244–259.

Referenced by

Complexity Class $\mathsf{D}_2^{\mathsf{P}}$

Complexity Class DP\mathsf{DP}

Reference

Referenced by

Complexity Class $\mathsf{DP}$