# 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)$. – Yuval Filmus Jan 30 '13 at 20:11
Check out Mahaney's theorem. – Pål GD Jan 30 '13 at 20:19
@PålGD Turn into an answer? (assuming the argument carries over to dense languages) – Yuval Filmus Feb 1 '13 at 4:40

This is 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 it's 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 summery, the answer is no unless $\mathsf{P}=\mathsf{NP}$. Note that if $\mathsf{P}=\mathsf{NP}$ then every non-trivial 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 fir 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. – Raphael Feb 2 '13 at 22:02
@Raphael: It is a proper answer. Did you check the link? – Tsuyoshi Ito Feb 2 '13 at 22:10
@TsuyoshiIto: Answers consisting only of a link are generally considered bad on SE; see here. – Raphael Feb 2 '13 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 '13 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. – Tsuyoshi Ito Feb 2 '13 at 23:42