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$
8
  • $\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$ Commented Feb 24, 2016 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$ Commented Feb 24, 2016 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$ Commented Feb 26, 2016 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$ Commented Feb 27, 2016 at 3:05
  • $\begingroup$ @MarzioDeBiasi Nice, Are you aware of articles that expand on your points? $\endgroup$ Commented Feb 27, 2016 at 11:20

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$ Commented Jan 30, 2023 at 17:26
  • $\begingroup$ Makes sense to me! $\endgroup$ Commented Jan 30, 2023 at 19:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.