1
$\begingroup$

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!

$\endgroup$
  • 5
    $\begingroup$ 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. $\endgroup$ – Joshua Grochow Jul 2 '14 at 15:36
7
$\begingroup$

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.

$\endgroup$

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.