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

<p>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.</p>

CC BY-SA 3.0
2014-02-27T18:02:04.070Z
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.
Andras Farago
CC BY-SA 3.0
2014-02-27T18:37:46.470Z
For Hamiltonian Path, see the original Berman-Hartmanis paper (Thm 7(5) in the STOC version, Thm 8(5) in the journal version: http://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: http://dx.doi.org/10.1016/0022-0000(78)90027-2
Joshua Grochow
CC BY-SA 3.0
2015-08-01T11:37:34.603Z
@JoshuaGrochow Is there a candidate non-natural example against BH conjecture?
Turbo
CC BY-SA 3.0
2015-08-06T22:10:00.817Z
@Turbo: Yes, the k-creative sets ("encrypted complete sets") of Joseph and Young 1985: http://dx.doi.org/10.1016/0304-3975(85)90140-9
Joshua Grochow
CC BY-SA 4.0
2021-03-11T09:28:07.030Z
@JoshuaGrochow Is there a natural or a non-natural candidate against BH if $P=NP$?
User2021
CC BY-SA 4.0
2021-03-11T17:48:01.920Z
@user2021 if P=NP then B-H fails, because finite sets are in P and aren't isomorphic to infinite sets.
Joshua Grochow
CC BY-SA 4.0
2021-03-12T13:34:46.440Z
@JoshuaGrochow Thank you.
User2021
CC BY-SA 3.0
2014-02-27T15:01:57.170Z
2014-02-27T15:01:57.170Z
Joshua Grochow
<p>The famous <a href="http://en.wikipedia.org/wiki/Berman%E2%80%93Hartmanis_conjecture"><strong>Isomorphism Conjecture</strong> of Berman and Hartmanis</a> 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 <em>paddable</em>, which is a nice, natural property, and implies p-isomorphism in a nontrivial way.</p>

<p>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  <em>natural</em> problems; they are constructed via diagonalization for the purpose of disproving the   Isomorphism Conjecture.</p>

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

CC BY-SA 3.0
2014-02-27T06:38:16.120Z
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.
Sasho Nikolov
CC BY-SA 3.0
2014-02-27T08:19:20.633Z
+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.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-02-27T15:04:44.130Z
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.
Joshua Grochow
CC BY-SA 3.0
2014-02-27T15:43:33.887Z
@MohammadAl-Turkistany I do not buy this analogy. Like I said, I am *not* against fuzzily defined notions in principle. Yes, an "algorithm" is hard to define but you know one when you see one. Same goes for example for "combinatorial proof". "Natural", however is a lot more vague than both of these examples, and I think it is worth trying to specify, *even informally*, some property that distinguishes natural from unnatural objects in the context of the question.
Sasho Nikolov
CC BY-SA 3.0
2014-02-27T17:19:40.227Z
@SashoNikolov I suggest that you post a question asking for properties that distinguish natural objects from unnatural ones in complexity theory.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-02-27T20:04:59.233Z
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.
Suresh Venkat
CC BY-SA 3.0
2014-02-27T20:57:09.407Z
@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.
Kaveh
CC BY-SA 3.0
2014-02-28T00:11:38.387Z
@Kaveh That's fair. I've seen this line get quite blurry as well (e.g. when we start with a general problem of clear independent interest and then start adding constraints), but I suppose we are in no such danger with this particular question. To Mohammad: I choose not to ask this question because I do not think there is a valid answer independent of specific context.
Sasho Nikolov
CC BY-SA 3.0
2014-02-28T03:28:46.060Z
a ref to any languages "not likely to be p-isomorphic to SAT" would be useful. anyway clearly this whole question hinges on a rather speculative/sketchy premise; even the "unnatural" examples have not been _proven_ to break the conjecture. it seems a bit strange/incongruous that for P=?NP, lack of finding P time algorithms after long search is taken as [circumstantial] evidence that P!=NP (ie _for_ the conjecture), but for isomorphism conjecture, lack of finding counterexamples after long search is taken as [circumstantial] evidence _against_ the conjecture (and the two are tightly coupled).
vzn
<cc.complexity-theory><complexity-classes><p-vs-np><np-complete>
Natural candidate against the Isomorphism Conjecture?
Andras Farago
# Natural candidate against the Isomorphism Conjecture?

(Asked by: username_0 on 2014-02-27)

The famous [**Isomorphism Conjecture** of Berman and Hartmanis](http://en.wikipedia.org/wiki/Berman%E2%80%93Hartmanis_conjecture) 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?

**Tags:** cc.complexity-theory, complexity-classes, p-vs-np, np-complete

> **Comments:**
> **username_1**: 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.  
> **username_2**: +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.  
> **username_3**: 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.  
> **username_1**: @MohammadAl-Turkistany I do not buy this analogy. Like I said, I am *not* against fuzzily defined notions in principle. Yes, an "algorithm" is hard to define but you know one when you see one. Same goes for example for "combinatorial proof". "Natural", however is a lot more vague than both of these examples, and I think it is worth trying to specify, *even informally*, some property that distinguishes natural from unnatural objects in the context of the question.  
> **username_2**: @SashoNikolov I suggest that you post a question asking for properties that distinguish natural objects from unnatural ones in complexity theory.  
> **username_4**: 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.  
> **username_5**: @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.  
> **username_1**: @username_5 That's fair. I've seen this line get quite blurry as well (e.g. when we start with a general problem of clear independent interest and then start adding constraints), but I suppose we are in no such danger with this particular question. To Mohammad: I choose not to ask this question because I do not think there is a valid answer independent of specific context.  
> **username_6**: a ref to any languages "not likely to be p-isomorphic to SAT" would be useful. anyway clearly this whole question hinges on a rather speculative/sketchy premise; even the "unnatural" examples have not been _proven_ to break the conjecture. it seems a bit strange/incongruous that for P=?NP, lack of finding P time algorithms after long search is taken as [circumstantial] evidence that P!=NP (ie _for_ the conjecture), but for isomorphism conjecture, lack of finding counterexamples after long search is taken as [circumstantial] evidence _against_ the conjecture (and the two are tightly coupled).  

---

## 1 answers

### Answer by username_3 on 2014-02-27. Score: 17 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  
> **username_3**: For Hamiltonian Path, see the original Berman-Hartmanis paper (Thm 7(5) in the STOC version, Thm 8(5) in the journal version: http://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: http://dx.doi.org/10.1016/0022-0000(78)90027-2  
> **username_7**: @JoshuaGrochow Is there a candidate non-natural example against BH conjecture?  
> **username_3**: @username_7: Yes, the k-creative sets ("encrypted complete sets") of Joseph and Young 1985: http://dx.doi.org/10.1016/0304-3975(85)90140-9  
> **username_8**: @JoshuaGrochow Is there a natural or a non-natural candidate against BH if $P=NP$?  
> **username_3**: @user2021 if P=NP then B-H fails, because finite sets are in P and aren't isomorphic to infinite sets.  
> **username_8**: @JoshuaGrochow Thank you.  

---

