We defined the class $\text{DP}$ like this:

$$\text{DP} := \{ A \setminus B : A, B \in \text{NP} \}$$

We say a problem $P$ is $\text{DP}$ complete iff $P \in \text{DP}$ and $X \leq P \forall X \in \text{DP}$, meaning that every language $X \in \text{DP}$ can be reduced to $P$ in polynomial time.

For a particular problem (which I do not expect you to solve, so I won't explain all the details), I already proved that $P \in \text{DP}$, but I do not know how to continue. Also, I could not find more information about this class.

Could someone give me a hint how to start such a proof or point me to further information about this complexity class which might help me to achieve it?

Edit: The definition is from a lecture about complexity of algorithms. The task is to prove that

$$\text{SAT-UNSAT} = \{\, (F,G) : F \text{ is satisfiable}, G \text{ is not}\, \}$$

is DP-complete. I proved that $\text{SAT-UNSAT} \in \text{DP}$, but I failed to prove the completeness.

  • $\begingroup$ What's the context in which you encountered this interesting question? Can you share more where it came from? Did you see this in a textbook? in a complexity theory course? Can you credit the source where it appeared? $\endgroup$
    – D.W.
    Commented Jun 9, 2017 at 17:45
  • $\begingroup$ What's the definition of $\leq$ here? Why is DP not the same as NP? $\endgroup$
    – Raphael
    Commented Jun 9, 2017 at 18:53
  • $\begingroup$ @D.W. I added some further details. As this is an internal document of the lecture, I don't think I can credit the source here. $\endgroup$ Commented Jun 10, 2017 at 11:06
  • $\begingroup$ @Raphael I added a note explaining it. $A \leq B$ (formally $A \leq_m^P B$) means that $A$ can be reduced to $B$ in polynomial time. $\endgroup$ Commented Jun 10, 2017 at 11:07
  • 1
    $\begingroup$ You absolutely have to credit the source, if only by the name of the author. $\endgroup$
    – Raphael
    Commented Jun 10, 2017 at 11:55

1 Answer 1


The DP-hardness of SAT-UNSAT is a direct consequence of the fact that SAT is NP-hard.

Suppose that $L \in \mathrm{DP}$. Then there exist languages $A \in \mathrm{NP}$ and $B \in \mathrm{coNP}$ such that $L = A \cap B$. Since SAT is NP-complete, there exists a polytime reduction $f$ such that $x \in A$ iff $f(x) \in \mathrm{SAT}$. Since UNSAT is coNP-complete, there exists a polytime reduction $g$ such that $x \in B$ iff $g(x) \in \mathrm{coSAT}$. You can check that the polytime reduction $h(x) = (f(x),g(x))$ satisfies $x \in L$ iff $h(x) \in \mathrm{SAT\text{-}UNSAT}$. This shows that SAT-UNSAT is DP-hard.

To complete the proof that SAT-UNSAT is DP-complete, you have to show that SAT-UNSAT is in DP. Presumably you already know how to do that.

Note that DP contains both SAT and UNSAT, and in particular differs from NP unless NP=coNP.

  • 1
    $\begingroup$ Thank you for your answer! But why isn't DP = NP? If a language is in $NP$, it must be in $DP$ as well ($L = L \setminus \varnothing$, and $L, \varnothing \in NP$). If a language $L = A \setminus B$ is in DP, we can simulate non-deterministic turing machines for $A$ and $B$ to decide $L$. Where is my mistake? $\endgroup$ Commented Jun 10, 2017 at 11:52
  • 1
    $\begingroup$ DP also contains coNP. Your argument would show that NP equals coNP, which is conjectured not to hold. I suggest reviewing the definition of non deterministic Turing machine. $\endgroup$ Commented Jun 10, 2017 at 11:55
  • $\begingroup$ I am sorry to bother you with this, but I cannot find a mistake in my attempt. Ahhhh are you referring to the fact that NTMs only complete in polynomial time for $x \in L$, but not in $x \notin L$? I never really managed to wrap my head around that. $\endgroup$ Commented Jun 10, 2017 at 12:02
  • $\begingroup$ I suggest dwelling on the difference between NP and coNP, and understanding why they are (probably) not the same. Take another look at their definitions. $\endgroup$ Commented Jun 10, 2017 at 12:16

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.