1
$\begingroup$

The class DP is defined as the set of all languages $L$ such that $L = L_1 \cap L_2$ where $L_1 \in NP$ and $L_2 \in coNP$.
For example, the language SAT-UNSAT is defined in the following manner ($\varphi$ is a $3-CNF$ formula):
$\{( \varphi, \varphi'): \varphi \in SAT \wedge \varphi ' \in UNSAT \}$. This language is the intersection of:
$$L_1 = \{ (\varphi, \varphi'): \varphi \in SAT \} $$ And:
$$ L_2 = \{ (\varphi, \varphi'): \varphi' \in UNSAT \}. $$

Given $L_1$ which is known to be a NP complete problem, and $L_2$ which is known to be coNP complete problem, does $L_1 \cap L_2$ necessarily DP complete?
(I believe that the answer is yes, because I can use the reduction of $L_1$ and $L_2$. But I am still not very confident in this idea.)

$\endgroup$
3
  • $\begingroup$ I suggest trying to spell out a proof, and see if it works. Be bold! $\endgroup$ Commented Jul 31, 2017 at 11:10
  • $\begingroup$ Since you haven't tried to check whether your idea works or write down a proof, you haven't given us much to work with. I suggest trying to prove it. You'll need to find an explicit reduction from any other DP language to $L_1 \cap L_2$. Part of your proof will need to define a way to do that. You might find that part of the challenge is how to construct a single reduction (not two). $\endgroup$
    – D.W.
    Commented Jul 31, 2017 at 16:17
  • $\begingroup$ If you give it a try yourself, you might either find that you can answer the question yourself (in which case you can write an answer below), or you get stuck at some specific point (and then you can edit your question to ask something more specific, and give us something concrete to respond to). $\endgroup$
    – D.W.
    Commented Jul 31, 2017 at 16:17

1 Answer 1

1
$\begingroup$

NO, it is not always so.

$L_1=\{<0,\varphi>|\varphi\ \mathrm{is\ satisfiable}\}$

$L_2=\{<1,\varphi>|\varphi\ \mathrm{is\ unsatisfiable}\}$

$L_1\cap L_2=\emptyset$

EDIT: As commented below by David Richerby, $L_1=SAT$ and $L_2=UNSAT$ would likewise falsify your claim in the question.

$\endgroup$
2
  • 1
    $\begingroup$ You don't need the "tupling", right? SAT and UNSAT are already disjoint. $\endgroup$ Commented Oct 11, 2018 at 17:13
  • $\begingroup$ No, I don't. And yes, that's right. $\endgroup$ Commented Oct 12, 2018 at 4:02

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.