The class DP is defined as the set of languages L for which there are two languages $L1 \in NP$ , $L2 \in coNP$ such that $L = L1 \cap L2$. (Do not confuse DP with $NP \cap coNP$, which may seem superficially similar.) Show that


(b) Every language in DP is polynomial-time reducible to EXACT INDSET.

Exercise 8, page 12

Clarifications: EXACT INDSET = {<G, k> : the largest independent set in G has size exactly k}.

Thoughts: I know that INDSET is NP-COMPLETE.


1 Answer 1


Hint: show that $\texttt{EXACT INDSET} = \texttt{INDSET}\cap L$ with: $$L = \{\langle G, k\rangle \mid G \text{ has no independent set of size }\geqslant k + 1\}$$ and show that $L$ is $\text{co}\mathsf{NP}$-complete.

  • $\begingroup$ can you help me a bit with proving that L is coNP-complete? $\endgroup$
    – Hjm
    Jan 10 at 8: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.