2
$\begingroup$

I would like to know how different defintions of class DP (also written $D^p$) are equivalent (brief explanations would do). The following are the two definitions I see:

  1. Difference between two NP problems; i.e., DP $:=\{A\setminus B\ :\ A,B\in NP\}$.
  2. $\{L_1\cap L_2\ :\ L_1\in \text{NP},\ L_2\in \text{co-NP} \}$.

Complexity zoo gives the full form "Difference Polynomial-Time" for DP and states that it is equivalent to BH$_2$. They give Definition 3 above as the definition of BH$_2$. (So, according to complexity zoo, the two definitions are equivalent).

This answer says that the definition of DP changed over time. Is this true? If so, which definition is accepted nowadays? Is there a book or survey that explains the complexity class DP (at least as a section) ?

According to this source, NP $\subseteq$ DP. Doesn't that mean DP-hard problems are NP-hard and the other direction is wrong (the latter, unless there is a collapse in complexity classes)?

Improve this question
$\endgroup$
1
  • $\begingroup$ The usual rule is one question per post. Which question do you want answered? Is your real question to ask for a proof of equivalence of these two definitions? If so, what have you tried? Are you familiar with the definition of co-NP? I suggest asking about $NP \subseteq DP$ as a separate question. If the two definitions are equivalent then it doesn't matter which one you choose. I'm not sure why it would matter which one is the "accepted" definition if they're equivalent; presumably everyone could use whichever one they prefer, with no harm to anyone? $\endgroup$
    – D.W. ♦
    Commented Apr 20, 2021 at 5:29

1 Answer 1

Reset to default
2
$\begingroup$

Equivalence follows immediately from the definitions. The definition of $\setminus$ is:

$$A \setminus B = A \cap \overline{B}$$

where $\overline{B} = \Sigma^* \setminus B$ denotes the complement of $B$. Now taking $L_1=A$ and $L_2=B$, it is trivial to prove that $L$ meets the first definition iff it meets the second definition, since $B \in NP$ iff $\overline{B} \in coNP$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Oh, I thought $A\setminus B$ meant something different (namely, acceptable words in $A$ minus acceptable words in $B$). $\endgroup$
    – Cyriac Antony
    Commented Apr 20, 2021 at 5:42
  • $\begingroup$ The choice of notation $A\setminus B$ is quite unfortunate. $\endgroup$
    – Cyriac Antony
    Commented Apr 20, 2021 at 11:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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