Cheap and Secure Web Hosting Provider : See Now

Definition of $D^P$?

, , No Comments
Problem Detail: 

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.

Asked By : John Threepwood

Answered By : Juho

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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback