<p>You are defining what is known as sparse sets. <a href="http://www.cs.umd.edu/~jkatz/complexity/f05/lecture6.pdf">Mahaney's theorem</a> 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.</p>

CC BY-SA 3.0
2014-07-02T13:09:50.330Z
2014-07-02T13:33:25.707Z
2014-07-02T13:33:25.707Z
Mohammad Al-Turkistany
<p>There is a result which goes along the lines of:</p>

<blockquote>
  <p><strong>Definition:</strong> 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$.</p>
  
  <p><strong>Theorem:</strong> 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)$.</p>
</blockquote>

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

<p>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.</p>

<p><strong>Example:</strong> 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.</p>

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

CC BY-SA 3.0
2014-07-02T15:36:49.967Z
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
<cc.complexity-theory>
Density of answers for NP complete problems?
gdiazc
# Density of answers for NP complete problems?

(Asked by: username_0 on 2014-07-02)

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!

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: 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 username_2 points out, the converse is true as well.  

---

## 1 answers

### Answer by username_2 on 2014-07-02. Score: 7 | Accepted answer

You are defining what is known as sparse sets. [Mahaney's theorem](http://www.cs.umd.edu/~jkatz/complexity/f05/lecture6.pdf) 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.


---

