# Natural candidate against the Isomorphism Conjecture?

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?

• 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 Feb 27 '14 at 6:38
• +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 Feb 27 '14 at 8:19
• 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 Feb 27 '14 at 15:04
• 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 Feb 27 '14 at 20:04
• @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 Feb 27 '14 at 20:57