Does the isomorphism conjecture imply exponential lower bounds on witnesses density? The Isomorphism Conjecture of Berman and Hartmanis states that all $NP$-complete sets are polynomial time isomorphic to each other. This means that $NP$-complete problems are efficiently reducible to each other via polynomial time computable and invertible bijections. The conjecture implies $P\neq NP$. 

The isomorphism conjecture implies an exponential lower bound on the density of $NP$-complete sets since Satisfiability problem is dense. I am wondering if it also implies an exponential lower bound on the density of witnesses for $NP$-complete set.


  Does the isomorphism conjecture imply exponential lower bounds on witnesses density? Does it imply that $NP$-complete problems can not be in $FewP$?


The best result I am aware of is the following:

If $P=UP$ and $NP=EXP$ then the isomorphism conjecture holds.

Density $D$ of a set $S$ refers to the number of strings of length less than $n$ in the language. A set $S$ is exponentially dense if its density is $D=\Omega(2^{n^\epsilon})$ for some $\epsilon \gt 0$ and for infinitely many $n$ and sparse if $D$= $O(poly(n))$.
I don't see how that would immediately follow: the isomorphism conjecture is about languages, and doesn't seem to have any implications about the witness structure of NP verifiers. (Every language has infinitely many different verifiers for it, and you could potentially rig those verifiers to do odd things.)

But your question reveals another very natural intriguing question, about the following strengthening of the Isomorphism Conjecture: 

"Are all verifiers for NP-complete sets poly-time isomorphic?" 

I.e., we want not only a poly-time isomorphism $\phi_{L,L'}$ between any two NP-complete languages $L,L'$ defined by verifiers $V,V'$, but also isomorphisms $\psi_{V,V'}$ between their sets of input-witness pairs which respect the isomorphism $\phi_{L,L'}$. (Note: There are multiple ways one might formally define this.) All $NP$-hardness proofs I can think of give you a one-to-one correspondence of this kind, as well. This stronger "Witness Isomorphism Conjecture" would imply some sort of yes-answer to your question.

A quick Google search (typing 'witness isomorphism conjecture') found a survey of some approaches to this kind of question:

Eric Allender. Investigations Concerning the Structure of Complete Sets. Perspectives in Computational Complexity: The Somenath Biswas Anniversary Volume, Springer, 2014