How can I prove DP completeness?

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.

• 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? – D.W. Jun 9 '17 at 17:45
• What's the definition of $\leq$ here? Why is DP not the same as NP? – Raphael Jun 9 '17 at 18:53
• @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. – just.kidding Jun 10 '17 at 11:06
• @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. – just.kidding Jun 10 '17 at 11:07
• You absolutely have to credit the source, if only by the name of the author. – Raphael Jun 10 '17 at 11:55

1 Answer

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.

• 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? – just.kidding Jun 10 '17 at 11:52
• 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. – Yuval Filmus Jun 10 '17 at 11:55
• 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. – just.kidding Jun 10 '17 at 12:02
• 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. – Yuval Filmus Jun 10 '17 at 12:16