16
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 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
    Commented Jan 30, 2013 at 20:11
  • 2
    $\begingroup$ Check out Mahaney's theorem. $\endgroup$
    – John K.
    Commented Jan 30, 2013 at 20:19
  • 2
    $\begingroup$ @PålGD Turn into an answer? (assuming the argument carries over to dense languages) $\endgroup$
    – Yuval Filmus
    Commented Feb 1, 2013 at 4:40

2 Answers 2

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • 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
    Commented Feb 2, 2013 at 22:02
  • $\begingroup$ @Raphael: It is a proper answer. Did you check the link? $\endgroup$
    – Tsuyoshi Ito
    Commented Feb 2, 2013 at 22:10
  • 5
    $\begingroup$ @TsuyoshiIto: Answers consisting only of a link are generally considered bad on SE; see here. $\endgroup$
    – Raphael
    Commented Feb 2, 2013 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
    Commented Feb 2, 2013 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
    Commented Feb 2, 2013 at 23:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.