19
$\begingroup$

The famous Isomorphism Conjecture of Berman and Hartmanis says that all $NP$-complete languages are polynomial time isomorphic (p-isomorphic) to each other. The key significance of the conjecture is that it implies $P\neq NP$. It was published in 1977, and a piece of supporting evidence was that all $NP$-complete problems known at the time were indeed p-isomorphic. In fact, they were all paddable, which is a nice, natural property, and implies p-isomorphism in a nontrivial way.

Since then, the trust in the conjecture deteriorated, because candidate $NP$-complete languages have been discovered that are not likely to be p-isomorphic to $SAT$, although the problem is still open. As far as I know, however, none of these candidates represent natural problems; they are constructed via diagonalization for the purpose of disproving the Isomorphism Conjecture.

Is it still true, after nearly four decades, that all known natural $NP$-complete problems are p-isomorphic to $SAT$? Or, is there any conjectured natural candidate to the contrary?

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ I will abstain from downvoting, but I am personally against all questions that ask for existence of something "natural" without defining what is natural. I am not saying I am against all "fuzzy" notions, but I think natural is too broad and some more concrete desirable/undesirable property should be further specified. $\endgroup$
    – Sasho Nikolov
    Commented Feb 27, 2014 at 6:38
  • 2
    $\begingroup$ +1 Nice question. @SashoNikolov , before the invention of Turing machines, the formal definition of algorithms, the intuitive notion was known and have been used for thousands of years. Lacking formal definition of natural problem should not deter us from using it informally. Natural problem is a concept that you know it when you see it. $\endgroup$
    – Mohammad Al-Turkistany
    Commented Feb 27, 2014 at 8:19
  • 4
    $\begingroup$ I agree with Mohammad that you typically know a natural problem when you see it. However, "natural" also depends on the context, and in some contexts there is a clearer notion - or perhaps just a more well-agreed-upon and large set of clearly natural examples - than in others. I think this particular case (NP-complete) problems falls into the former class. For example, applying a one-way function to SAT to get another NP-complete problem (the basic idea behind some of the candidates violating Berman-Hartmanis) clearly results in an "unnatural" problem. $\endgroup$
    – Joshua Grochow
    Commented Feb 27, 2014 at 15:04
  • 4
    $\begingroup$ The problem with 'natural' in practice here on cstheory.SE is that the question usually results in a 'no true scotsman' storm where each answer that the OP doesn't like is deemed to be "unnatural" for an evolving/shifting set of reasons. $\endgroup$
    – Suresh Venkat
    Commented Feb 27, 2014 at 20:04
  • 6
    $\begingroup$ @Sasho, I personally read "natural" without further clarification as meaning: it is not an artificially made up problem to answer the question (or similar ones), people are interested in the problem independently. $\endgroup$
    – Kaveh
    Commented Feb 27, 2014 at 20:57

1 Answer 1

Reset to default
17
$\begingroup$

I think the answer is yes, even today there is no known natural problem that is a candidate for violating the Isomorphism Conjecture.

The primary reason is that typically natural NP-complete problems are very easily seen to be paddable, which Berman and Hartmanis showed suffices to be isomorphic to SAT. For natural graph-related problems this typically involves adding extra vertices that are, e.g., disconnected from the graph, or connected in a very particular (but usually obvious) way. For the decision version of optimization problems, it typically involves adding new dummy variables with no constraints on them. And so on.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ Yes, in most graph problems the padding is easy. But this may not always hold. An example: is it true that the graph is triangle free and has a Hamiltonian path? Here, to preserve the property, a new padding vertex must connect to some old (to allow Hamiltonian path), it must connect to an independent set (to avoid creating a triangle), and this independent set must be such that it contains an endpoint of at least one Hamiltonian path (to make it extendable to the new vertex). It does not look obvious to me how to achieve this. Of course, one might find some other way to pad, I'm not sure. $\endgroup$
    – Andras Farago
    Commented Feb 27, 2014 at 18:02
  • 4
    $\begingroup$ For Hamiltonian Path, see the original Berman-Hartmanis paper (Thm 7(5) in the STOC version, Thm 8(5) in the journal version: dx.doi.org/10.1137/0206023). Their construction does not introduce any new directed 3-cycles. If you want to avoid even undirected triangles you can subdivide some of the edges in their construction with new vertices. You might also find their follow-up paper interesting, in which they show quadratic Diophantine equations are p-iso to SAT: dx.doi.org/10.1016/0022-0000(78)90027-2 $\endgroup$
    – Joshua Grochow
    Commented Feb 27, 2014 at 18:37
  • 1
    $\begingroup$ @JoshuaGrochow Is there a candidate non-natural example against BH conjecture? $\endgroup$
    – Turbo
    Commented Aug 1, 2015 at 11:37
  • 2
    $\begingroup$ @Turbo: Yes, the k-creative sets ("encrypted complete sets") of Joseph and Young 1985: dx.doi.org/10.1016/0304-3975(85)90140-9 $\endgroup$
    – Joshua Grochow
    Commented Aug 6, 2015 at 22:10
  • $\begingroup$ @JoshuaGrochow Is there a natural or a non-natural candidate against BH if $P=NP$? $\endgroup$
    – User2021
    Commented Mar 11, 2021 at 9:28

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.