<p>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 &quot;direct and natural&quot; 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 &quot;polynomial-time recodings&quot; in their introduction, though they don't delve further in this direction.)</p>
<p>Several types of examples:</p>
<p>Example Type 1: Two different string encodings built from &quot;conceptually the same&quot; language. For example, we may encode CNF-SAT instances into <span class="math-container">$\Sigma^*$</span> where <span class="math-container">$\Sigma = \{(,),x,0,1,\wedge,\vee, \neg\}$</span> 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 <span class="math-container">$\{0,1\}^*$</span> (for example, using a prefix-free encoding of <span class="math-container">$\Sigma$</span>). All of these different encodings should yield p-isomorphic languages, where the p-isomorphism is basically to translate from one encoding to the other.</p>
<p>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 &quot;two different encodings of the same language into strings&quot; and &quot;using two different data structures to encode the same objects&quot;, but conceptually Type 2 feels a bit more specific than Type 1. Maybe it is a sub-type.)</p>
<p>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 <span class="math-container">$k$</span> iff it has a vertex cover of size <span class="math-container">$|V|-k$</span>. So the isomorphism here is given by mapping <span class="math-container">$(G,k)$</span> (an IndSet instance) to <span class="math-container">$(G,|V|-k)$</span>. As a less trivial possible example, I would be surprised if one could not directly make the holographic equivalence between #<span class="math-container">$_2$</span>MonRtw3CNF and #<span class="math-container">$_2$</span>IndSet for cubic graphs from Valiant/Guo-Lu-Valiant into a p-isomorphism, though I have not worked it out carefully.</p>

CC BY-SA 4.0
2023-01-30T17:26:59.847Z
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
CC BY-SA 4.0
2023-01-30T19:25:30.683Z
Makes sense to me!
Joshua Grochow
CC BY-SA 4.0
2023-01-26T06:10:53.157Z
2023-01-26T06:10:53.157Z
Joshua Grochow
<p>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 <em>labelings</em> for some language and should be related via permutations.</p>

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

<p><strong>Motivation:</strong> 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.   </p>

CC BY-SA 3.0
2016-02-24T16:49:49.873Z
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
CC BY-SA 3.0
2016-02-24T17:50:19.357Z
@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
CC BY-SA 3.0
2016-02-26T17:30:29.700Z
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
CC BY-SA 3.0
2016-02-27T03:05:57.267Z
@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
CC BY-SA 3.0
2016-02-27T11:20:19.847Z
@MarzioDeBiasi Nice, Are you aware of articles that expand on your points?
Mohammad Al-Turkistany
CC BY-SA 3.0
2016-02-27T15:52:58.930Z
@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
CC BY-SA 3.0
2016-02-27T23:37:30.837Z
@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
CC BY-SA 3.0
2016-03-03T18:12:41.323Z
suggest it might help to start by defining "paddability" in a formal/ technical way
vzn
<cc.complexity-theory><permutations>
Proving P-Isomorphism between two languges
Mohammad Al-Turkistany
# Proving P-Isomorphism between two languges

(Asked by: username_0 on 2016-02-24)

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.

**Tags:** cc.complexity-theory, permutations

> **Comments:**
> **username_1**: 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"?  
> **username_0**: @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?  
> **username_2**: 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)$.  
> **username_3**: @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.  
> **username_0**: @MarzioDeBiasi Nice, Are you aware of articles that expand on your points?  
> **username_2**: @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) ...  
> **username_1**: @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.  
> **username_4**: suggest it might help to start by defining "paddability" in a formal/ technical way  

---

## 1 answers

### Answer by username_1 on 2023-01-26. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_0**: 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?  
> **username_1**: Makes sense to me!  

---

