# Density of answers for NP complete problems?

There is a result which goes along the lines of:

Definition: For every language $L$, define $L_n = \{ w \in L \mid \text{length}(w) = n \}$, i.e. the subset of $L$ of words whose length is $n$.

Theorem: If $\mathbf{P} = \mathbf{NP}$, then for every $\mathbf{NP}$-complete language $L$ there exists a polynomial $p : \mathbb{N} \rightarrow \mathbb{N}$ such that for every integer $n$ it is the case that $|L_n| \leq p(n)$.

The intuition of the theorem is that if $\mathbf{P} = \mathbf{NP}$, then $\mathbf{NP}$-complete languages have a polynomial density of solutions.

As we believe that $\mathbf{P} \neq \mathbf{NP}$, we should tend to believe the contrary, i.e. that $\mathbf{NP}$-complete problems do not have a polynomial density of solutions.

Example: For the case of 3-coloring, for large $n$ there are many 3-colorable graphs with $n$ nodes; in any case, the number of 3-colorable graphs is not bounded by a polynomial.

Does anyone recognise this result? What is the actual statement of the theorem? Any reference would be welcome!

• Your theorem as stated currently is false. For example, the language consisting of all strings except for the string 0 is trivially in $\mathsf{P}$, obviously not polynomially sparse, and is $\mathsf{NP}$-complete if $\mathsf{P} = \mathsf{NP}$. I believe what you meant to say is: If $\mathsf{P}=\mathsf{NP}$, then there exists an $\mathsf{NP}$-complete language that is polynomially sparse. And as Mohammad Al-Turkistany points out, the converse is true as well. – Joshua Grochow Jul 2 '14 at 15:36

You are defining what is known as sparse sets. Mahaney's theorem states that sparse $NP$-complete (under Karp reduction ) sets exist if and only if $P=NP$. So, your theorem is just one direction of that theorem.