Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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
(a) EXACT INDSET ∈ DP.
(b) Every language in DP is polynomial-time reducible to EXACT INDSET.
Clarifications: EXACT INDSET = {<G, k> : the largest independent set in G has size exactly k}.
Thoughts: I know that INDSET is NP-COMPLETE.
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.
