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.
