Problem Detail: 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?
Asked By : Jernej
Answered By : Kaveh
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/9327
