# EXACT INDSET is DP-complete

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.

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.

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.