# Proving P-Isomorphism between two languges

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.

• 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"? Feb 24, 2016 at 16:49
• @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? Feb 24, 2016 at 17:50
• 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)$. Feb 26, 2016 at 17:30
• @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. Feb 27, 2016 at 3:05
• @MarzioDeBiasi Nice, Are you aware of articles that expand on your points? Feb 27, 2016 at 11:20

Example Type 1: Two different string encodings built from "conceptually the same" language. For example, we may encode CNF-SAT instances into $$\Sigma^*$$ where $$\Sigma = \{(,),x,0,1,\wedge,\vee, \neg\}$$ in the obvious way, using the bits 0,1 to encode the indices of the variables. Or we might choose any of a number of encodings of CNF-SAT into $$\{0,1\}^*$$ (for example, using a prefix-free encoding of $$\Sigma$$). All of these different encodings should yield p-isomorphic languages, where the p-isomorphism is basically to translate from one encoding to the other.
Example Type 3: Problems that are very easily seen to be equivalent. For example, Clique and Independent Set. If graphs are encoded by adjacency matrices, the p-isomorphism here can literally be given by swapping 0s and 1s. As another example, consider IndSet and VertexCover. Recall a graph has an independent set of size $$k$$ iff it has a vertex cover of size $$|V|-k$$. So the isomorphism here is given by mapping $$(G,k)$$ (an IndSet instance) to $$(G,|V|-k)$$. As a less trivial possible example, I would be surprised if one could not directly make the holographic equivalence between #$$_2$$MonRtw3CNF and #$$_2$$IndSet for cubic graphs from Valiant/Guo-Lu-Valiant into a p-isomorphism, though I have not worked it out carefully.