2
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\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.♦ Jun 9 '17 at 17:45
  • $\begingroup$ What's the definition of $\leq$ here? Why is DP not the same as NP? $\endgroup$ – Raphael♦ Jun 9 '17 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$ – just.kidding Jun 10 '17 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$ – just.kidding Jun 10 '17 at 11:07
  • 1
    $\begingroup$ You absolutely have to credit the source, if only by the name of the author. $\endgroup$ – Raphael♦ Jun 10 '17 at 11:55
4
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 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$ – just.kidding Jun 10 '17 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$ – Yuval Filmus Jun 10 '17 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$ – just.kidding Jun 10 '17 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$ – Yuval Filmus Jun 10 '17 at 12:16

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.