8
$\begingroup$

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))$.

Improve this question
$\endgroup$
2
  • $\begingroup$ Witnesses density of set $X$ depends on the maximum number of witnesses for $x$ over all $x \in X$. $\endgroup$
    – Mohammad Al-Turkistany
    Commented Nov 7, 2015 at 13:52
  • $\begingroup$ Seems unlikely. It'd be interesting to construct an oracle where the isomorphism conjecture holds and $NP=UP$ or $NP=FewP$... (Note that making $NP=UP$ may make life a little harder in this construction, since to get the isomorphism conjecture to hold one would then need $P \neq UP$, and yet still need another way around the Joseph-Young Conjecture.) $\endgroup$
    – Joshua Grochow
    Commented Nov 8, 2015 at 14:43

1 Answer 1

Reset to default
13
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ +1 Very interesting. Follwing on your suggestion, I googled and I found this paper, Witness-isomorphic reductions and the local search problem. Is this the kind of required witness isomorphism ? $\endgroup$
    – Mohammad Al-Turkistany
    Commented Nov 8, 2015 at 11:40
  • 5
    $\begingroup$ Interesting! Do you want to say that for every $L,L'$ that are $\mathsf{NP}$-complete, there exist verifiers $V,V'$ and compatible isomorphisms $\phi_{L,L'}, \psi_{V,V'}$? Or really for every pair of verifiers $V,V'$, there exists compatible isos? Since your notion of compatible isos in particular implies parsimonious reductions both ways, the second question is easily falsified: take any verifier $V$ for SAT, then let $V'$ be a verifier for SAT that accepts every witness in $\{\{0,1\}^n w | V(w)=1\}$. $\endgroup$
    – Joshua Grochow
    Commented Nov 8, 2015 at 14:40
  • 1
    $\begingroup$ Right, you have to be careful how you formulate the conjecture to avoid trivial counterexamples. Googling revealed to me that I am not the first, so I suggest reading the work of people who have thought about this for more than 10 minutes :) $\endgroup$
    – Ryan Williams
    Commented Nov 8, 2015 at 15:10
  • $\begingroup$ Ryan, I think your conjecture is very important. It may be easier to prove than the standard Isomorphism Conjecture of Berman and Hartmanis. I think your conjecture suggests the existence of universal verifier for all NP sets. $\endgroup$
    – Mohammad Al-Turkistany
    Commented Nov 8, 2015 at 15:18

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.