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?

  • 1
    $\begingroup$ There is a related notion of sparse languages, in which the condition is just the opposite: $|J \cap \Sigma^n| \leq p(n)$. $\endgroup$ – Yuval Filmus Jan 30 '13 at 20:11
  • 2
    $\begingroup$ Check out Mahaney's theorem. $\endgroup$ – Pål GD Jan 30 '13 at 20:19
  • 2
    $\begingroup$ @PålGD Turn into an answer? (assuming the argument carries over to dense languages) $\endgroup$ – Yuval Filmus Feb 1 '13 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.

  • 1
    $\begingroup$ This does not give more than the comment (which is not even yours). Please elaborate to make a proper answer out of this post. $\endgroup$ – Raphael Feb 2 '13 at 22:02
  • $\begingroup$ @Raphael: It is a proper answer. Did you check the link? $\endgroup$ – Tsuyoshi Ito Feb 2 '13 at 22:10
  • 5
    $\begingroup$ @TsuyoshiIto: Answers consisting only of a link are generally considered bad on SE; see here. $\endgroup$ – Raphael Feb 2 '13 at 22:52
  • $\begingroup$ @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. $\endgroup$ – Reza Feb 2 '13 at 23:00
  • $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Feb 2 '13 at 23:42

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.