3
$\begingroup$

What is the definition of the complexity class $D^P$?

In recent papers I sometimes read $D^P$ but could not find a definition of it. Unfortunately Complexity Zoo does not give one, too.

Is it the same as: "A language L is in the class $DP$ if and only if there are two languages $L_1\in NP$ and $L_2\in coNP$ such that $L = L_1\cap L_2$" (Def. 17.1 from Papadimitriou - Computational Complexity (1994))?

Note: In the stated definition it says $DP$ not $D^P$. But I was wondering if it is the same.

$\endgroup$
3
$\begingroup$

The class $\mathsf{D^p}$ was originally introduced in the context of studying the facets of the traveling salesman polytope. It contains all languages that can be considered as the intersection of a language in $\sf NP$ and one in $\sf co\text{-}NP$. Formally, $\mathsf{D^p} = \{ L_1 \cap \overline{L_2} \mid L_1,L_2 \in \mathsf{NP} \}$. It first appeared in [1].


[1] Papadimitriou, Christos H., and Mihalis Yannakakis. "The complexity of facets (and some facets of complexity)." Journal of Computer and System Sciences 28.2 (1984): 244-259.

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