15
$\begingroup$

I have the impression that for every NP-complete problem, for infinitely many input sizes $n$, the number of yes-instances over all possible inputs of size $n$, is (at least) exponential in $n$.

Is this true? Can it be proven (probably only under the assumption that $P\neq NP$)? Or can we, maybe artificially, find a problem where for all (large enough) $n$, the number of yes-instances is at most polynomial in $n$?

My reasoning is basically that given a yes-instance for 3-SAT, we can identify the literal in each clause that makes it true and replace another variable in the clause with yet another variable, without changing that it's satisfiable. Since we could do that with each clause, it leads to an exponential number of yes-instances. The same holds for many other problems such as hamiltonian path: we can freely change edges that are not on the path. I then vagely reason that since reducibility is involved where in some way solutions must be kept, it must hold for all NP-complete problems.

It seems also to hold for the maybe NP-intermediate problem of graph isomorphism (where we can freely apply the same changes to both graphs if we know the mapping). I wonder if it also holds for integer factorization.

$\endgroup$
19
$\begingroup$

A language with only polynomially many yes-instances is called sparse. Mahaney's theorem states that if any NP-complete language is sparse, then P = NP. Since most people expect that P $\ne$ NP, it seems unlikely that there exists a NP-complete language with only polynomially many yes-instances.

It's a separate question whether the number of yes-instances is exponential. (One could imagine that the number of yes-instances might be more than polynomial but less exponential.) The Berman-Hartmanis conjecture is relevant here; it implies that all NP-complete problems have exponentially many yes-instances. The conjecture remains an open problem.

$\endgroup$

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.