Proving P-Isomorphism between two languges

Question

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"? — Joshua Grochow, Feb 24 '16 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? — Mohammad Al-Turkistany, Feb 24 '16 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)$. — Marzio De Biasi, Feb 26 '16 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. — Andras Farago, Feb 27 '16 at 03:05
@MarzioDeBiasi Nice, Are you aware of articles that expand on your points? — Mohammad Al-Turkistany, Feb 27 '16 at 11:20
@MohammadAl-Turkistany: no, they are simple considerations. BTW I must think more about the $K(y|x)$ ... it doesn't make much sense; but it could be an interesting argument to study : the p-isomorphism $f$ must preserve the Kolmogorov complexity of the instances ($K(x) = K(f(x))+c$) (immediate); but for yes instances it is also a mapping between the set of solutions of $x$ and the set of solutions of $f(x)$ (it clearly doesn't map the single solutions, and the difference between the number of solutions of $x$ and $f(x)$ can be exponientially large) ... — Marzio De Biasi, Feb 27 '16 at 15:52
@AndrasFarago: Indeed, p-isomorphism is only a bijection between the entire infinite languages (and, respectively, their complements). I wrote that comment before the analogy with GI was mentioned. — Joshua Grochow, Feb 27 '16 at 23:37
suggest it might help to start by defining "paddability" in a formal/ technical way — vzn, Mar 03 '16 at 18:12

score 2 · Accepted Answer · answered Jan 26 '23 at 06:10

While I don't know other general properties (similar to paddability) that imply p-isomorphism, I suppose there is another way that is perhaps more "direct and natural" in the way asked for. Namely, if you can show that two languages are really encoding the same thing. (Indeed, Berman and Hartmanis refer to p-isomorphisms as "polynomial-time recodings" in their introduction, though they don't delve further in this direction.)

Several types of examples:

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 2: Using two different data structures to encode the same thing. For example, if you consider the Graph 3-Coloring problem where the input is adjacency matrices, this should be p-isomorphic to one where the input is adjacency lists, incidence matrices, or edge lists. (I guess this is similar to type 1 - if pressed, I suppose I would find it hard to give a technical distinction between "two different encodings of the same language into strings" and "using two different data structures to encode the same objects", but conceptually Type 2 feels a bit more specific than Type 1. Maybe it is a sub-type.)

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.

Thanks Joshua, I guess another example would be encoding some integer value using binary and decimal systems. The encoding efficiency of both systems is related by some constant. Meanwhile, encoding NP problems using 3sat is exponentially more efficient than encoding them using Horn 3SAT. Does this make sense? — Mohammad Al-Turkistany, Jan 30 '23 at 17:26

Proving P-Isomorphism between two languges

1 Answers1

Linked