6
$\begingroup$

The famous Isomorphism Conjecture states that all NP-complete problems are isomorphic via polynomial-time computable and invertible bijections (reductions). Padability is the only property that I know which can be used to show P-isomorphism between two languages (The most direct way is to present the reduction). My intuition suggests that two p-isomorphic languages are two different labelings for some language and should be related via permutations.

What other techniques (or properties) can be used to show that two languages are P-isomorphic?

Motivation: I am trying to extend an analogy from GI. If two graphs are isomorphic then they are just two different labelings of the same mathematical structure. I guess there should be more natural and direct way than padability.

$\endgroup$
  • $\begingroup$ I'm not sure I know of any other general properties that imply p-isomorphism; will be cool if you get any answers. I don't see why you call your last statement an "intuition"; it is simply true. The p-computable and p-invertible bijection is a permutation. What do you mean by "labeling"? $\endgroup$ – Joshua Grochow Feb 24 '16 at 16:49
  • $\begingroup$ @JoshuaGrochow Yes, mathematically, bijections are permutations. However, I am looking for more direct technique for exhibiting permutation between two NP-complete languages. I am trying to extend analogy from GI. If two graphs are isomorphic then they are just two different labelings of the same mathematical structure. I guess there should be more natural and direct way than padability. Did that help? $\endgroup$ – Mohammad Al-Turkistany Feb 24 '16 at 17:50
  • $\begingroup$ Another (obvious) property is that the P-isomorphism is "local"; the elements of language $x \in L_1, a \leq x \leq b $ are not mapped "far away" from $a,b$, so picking as reference language $SAT$, you rule out NPC sparse languages. As a bijection, it also preserves the Kolmogorov complexity of the instances $K(x)$ and the combined Kolmogorov Complexity instances+solutions $K(y | x)$. $\endgroup$ – Marzio De Biasi Feb 26 '16 at 17:30
  • $\begingroup$ @JoshuaGrochow Unless I misunderstood something, I don't think that p-isomorphism is just a permutation in the same simple, finite sense as graph isomorphism. For example, isomorphic graphs must have the same number of vertices and edges etc., while p-isomorphic languages may have different number of n-bit strings, for any n. Of course, we have a bijection (permutation) between the entire (infinite) languages, but this is much less simple than what we have between two graphs, because p-isomorphism may not be a bijection between any finite subsets. $\endgroup$ – Andras Farago Feb 27 '16 at 3:05
  • $\begingroup$ @MarzioDeBiasi Nice, Are you aware of articles that expand on your points? $\endgroup$ – Mohammad Al-Turkistany Feb 27 '16 at 11:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.