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.)

Improve this question
$\endgroup$
3
  • $\begingroup$ I suggest trying to spell out a proof, and see if it works. Be bold! $\endgroup$
    – Yuval Filmus
    Jul 31 '17 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. ♦
    Jul 31 '17 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. ♦
    Jul 31 '17 at 16:17
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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ You don't need the "tupling", right? SAT and UNSAT are already disjoint. $\endgroup$
    – David Richerby
    Oct 11 '18 at 17:13
  • $\begingroup$ No, I don't. And yes, that's right. $\endgroup$
    – Thinh D. Nguyen
    Oct 12 '18 at 4:02

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.