# A dense NP complete language implies P=NP

We say that the language $J \subseteq \Sigma^{*}$ is dense if there exists a polynomial $p$ such that $$|J^c \cap \Sigma^n| \leq p(n)$$ for all $n \in \mathbb{N}.$ In other words, for any given lenght $n$ there exist only polynomially many words of length $n$ that are not in $J.$

The problem I am currently studying asks to show the following

If there exist a dense $NP$-complete language then $P = NP$

What the text suggest is to consider the polynomial reduction to $3$-$SAT$ and then construct an algorithm that tries to satisfy the given $CNF$ formula while also generating elements in $J^c.$

What I am wondering is

Is there a more direct proof? Is this notion known in a more general setting?

• There is a related notion of sparse languages, in which the condition is just the opposite: $|J \cap \Sigma^n| \leq p(n)$. Jan 30, 2013 at 20:11
• Check out Mahaney's theorem. Jan 30, 2013 at 20:19
• @PålGD Turn into an answer? (assuming the argument carries over to dense languages) Feb 1, 2013 at 4:40

This is a nice homework problem about Mahaney's theorem.

Note that the complement of a "dense" language is a sparse language. Moreover if a language is $\mathsf{NP}$-complete its complement is $\mathsf{coNP}$-complete.

If there is a "dense" $\mathsf{NP}$-complete language, there is a sparse $\mathsf{coNP}$-complete language.

Mahaney's theorem tells us that there is no sparse $\mathsf{NP}$-complete language unless $\mathsf{P}=\mathsf{NP}$.

We can adopt the proof to show that there is no sparse $\mathsf{coNP}$-complete language unless $\mathsf{P}=\mathsf{coNP}$ which is equivalent to $\mathsf{P}=\mathsf{NP}$ (since $\mathsf{P}$ is closed under complements).

In summary, the answer is no unless $\mathsf{P}=\mathsf{NP}$. Note that if $\mathsf{P}=\mathsf{NP}$ then every nontrivial language is $\mathsf{NP}$-complete.

ps: You may want to try the following and then use Mahaney's theorem: there is a sparse $\mathsf{NP}$-complete set iff there is a sparse $\mathsf{coNP}$-complete set. However I doubt that a proof for this statement would be much easier than a proof for Mahaney's theorem.

As mentioned above according to Mahaney's theorem. Sparse and dense languages could not be $NP-Hard$ unless $P=NP$.

The mentioned draft contains complete proof.

• This does not give more than the comment (which is not even yours). Please elaborate to make a proper answer out of this post. Feb 2, 2013 at 22:02
• @Raphael: It is a proper answer. Did you check the link? Feb 2, 2013 at 22:10
• @TsuyoshiIto: Answers consisting only of a link are generally considered bad on SE; see here. Feb 2, 2013 at 22:52
• @Raphael: The question answered was solved before in literature. The link contains whole proof (which is 6 pages). I think if he has more questions we could continue with discussion.
– Reza
Feb 2, 2013 at 23:00
• @Raphael: Silly. A link is better than nothing. If you want, elaborate the answer by yourself instead of blaming a user for posting a useful link. Feb 2, 2013 at 23:42