<p>Yes, but I'm not sure it means much. Yes in a trivial way: suppose $\varphi$ is an isomorphism between two $\mathsf{NP}$-complete languages $L_1, L_2$, and $L_1$ exhibits a phase transition with respect to some parameter $m(x)$. Then so does $L_2$, with respect to the parameter $m_2(y) := m(\varphi^{-1}(y))$. (This relies on the fact that "phase transition" talks about the fraction of satisfiable instances jumping from 0 to 1, as a fraction of an exponential number of instances of a given size, and p-isomorphisms preserve densities up to a polynomial.)</p>

<p>I'm not sure this is such a meaningful statement, however, because the parameter $m_2$ above can be totally unnatural from the point of view of $L_2$. Most phase transitions of interest are with respect to some natural parameter (e.g. clause-to-variable ratio in k-SAT, density of a graph, etc.). But those natural parameters are defined in terms of some "internal" structure to the instances, not by just treating the problem instances as abstract strings in $\Sigma^*$ ($\Sigma$ your finite alphabet). But p-isomorphism <em>does</em> just treat inputs as abstract strings, and "knows nothing" about the internal structure that we like to impose on them. So, sure, you can say that all paddable languages have a phase transition since k-SAT does. But that doesn't tell you if, for example, solvability of quadratic Diophantine equations exhibits a phase transition in terms of any parameter that is natural from the point of view of Diophantine equations...</p>

CC BY-SA 3.0
2016-02-29T20:39:32.780Z
Thank you, the answer is formally correct, but I realized that I did not phrase the question well enough to express what I am really interested in. It is this: if $L_1$ exhibits phase transition within the set of $n$-bit instances (for any $n$), does this imply that $L_2$ also exhibits phase transition in the same sense? Note that the mapping $m_2(y) := m(\varphi^{-1}(y))$ of the order parameter may not imply it, because it may map n-bit instances to instances of varying length. Therefore, it is not clear if $L_2$ has phase transition for  instances of length n.
Andras Farago
CC BY-SA 3.0
2016-02-29T21:18:32.390Z
Okay. Are you sure that's what you want to ask? Length is not preserved by p-isomorphism except up to polynomials. And, under the standard encoding of k-SAT, the phase transition in k-SAT is *not* among instances of the same length. Of course, you can use a different encoding, such as saying that all n-variable instances of k-SAT will be strings of length $2^k \binom{n}{k}$ (or whatever the exact right number is) indicating which clauses are present, but that's not exactly a natural encoding. Note that these two encodings are p-isomorphic, however.
Joshua Grochow
CC BY-SA 3.0
2016-02-29T23:58:14.047Z
Well, I guess, I still did not phrase the question right. What I have in mind is shown by this example: fix some parameter, such as the number of vertices in a graph, and vary another parameter, such as the number of edges. Depending on the encoding, this indeed may not mean that we stay within the set of strings of the same length. Now, if we know that a graph property has phase transition according to this order parameter (the density of the graph), does this imply that another language, describing another graph property, preserves phase transition, if the languages are P-isomorphic?
Andras Farago
CC BY-SA 3.0
2016-03-01T00:36:36.900Z
@AndrasFarago: Okay, excellent. But now I think a small variant of my answer still gives a positive-but-kind-of-trivial answer: let $n(x)$ be the number of vertices of the graph $x$, and $d(x)$ the density of edges. Let $L$ be your favorite NPC language with a phase transition in $d$ ("relative to" $n$, as you describe). Let $L'$ be p-isomorphic to $L$ via $\varphi$. Then $L'$ exhibits a phase transition in $d(\varphi(x))$ "relative to" $n(\varphi(x))$.
Joshua Grochow
CC BY-SA 3.0
2016-03-01T06:12:56.410Z
I think what Andras wants to know is the following (please correct me if I am wrong). Lets say you have an NP-Complete problem A with a phase-transition at density x, where x is in between (0-1). Then he wants to map that problem to some other NP-Complete problem B with a phase transition at density y. The question is does the instances at density x for problem A correspond to the instances at density y for problem B. Is it 1-1?
Tayfun Pay
CC BY-SA 3.0
2016-03-01T17:30:16.630Z
@JoshuaGrochow The problem is that after the mapping we get a different type of phase transition, because both the parameter $d$, and the "base" $n$ are transformed. What I would like to know is this: If $L_1$ has a phase transition in $d$ "relative to" $n$, and $L_1, L_2$ are p-isomorphic, does this imply that $L_2$ also has a phase transition in some (possibly transformed) parameter $d'$, but still relative to the _same_ base $n$?
Andras Farago
CC BY-SA 3.0
2016-03-01T17:39:40.467Z
@AndrasFarago: But what do you mean by two different languages having the same base? That is, if $L_1$ is a graph problem where $n(x)$ is the number of vertices, and $L_2$ is an arbitrary subset of $\Sigma^*$ that is isomorphic to $L_1$, then what do you mean by "the same n" for $L_2$? Or do you have in mind that $L_1$ and $L_2$ are both natural graph problems that you know to be isomorphic? If the latter, one would have to examine the isomorphism to see if it preserved n; that seems very unlikely to me though, given the BH construction.
Joshua Grochow
CC BY-SA 3.0
2016-03-01T20:38:24.077Z
@JoshuaGrochow The "same base" I originally had in mind was simply the instance size, regardless to whether it is a graph problem or not. If $L_1$ is a language that has phase transition over $n$-bit strings, according to some order parameter $d$, does this imply that a p-isomorphic $L_2$ also has phase transition over $n$-bit strings, according to some order parameter $d'$? (Let us assume an encoding that keeps the instance length constant for varying order parameter.)
Andras Farago
CC BY-SA 3.0
2016-03-01T20:43:48.100Z
@AndrasFarago: I'm not sure that string length is particularly privileged as an example function "n" when talking about p-isomorphisms. I think my answer and previous comments essentially already addressed this: it is unlikely to be true, since p-isomorphism only preserves length up to polynomials, and the only way I see to transfer an order parameter $d$ across a p-isomorphism is as above (that is, $d(\varphi(y))$).
Joshua Grochow
CC BY-SA 3.0
2016-02-29T05:37:21.383Z
2016-02-29T05:37:21.383Z
Joshua Grochow
<p>Consider two NP-complete languages that are polynomial-time isomorphic. If we know that one of them exhibits phase transition (with respect to some order parameter), does this imply that the other must also have phase transition, with respect to some (possibly different) order parameter?</p>

<p>Intuitively, I would expect that the answer is yes. The reason is that p-isomorphmism means that the two languages are "essentially the same," apart from a polynomial-time re-encoding. It would appear quite surprising if one of them has phase transition, while the other does not, despite their p-isomorphism. But how can the implication be proved formally?</p>

CC BY-SA 3.0
2016-02-28T18:12:15.287Z
Can you give an example of a P-time isomorphism between two NP-complete languages?
Zirui Wang
CC BY-SA 3.0
2016-02-28T19:16:59.187Z
@ZiruiWang A very simple example is between Max Clique and and Max Independent Set. But there are many more (infinitely many), since it is known that all paddable NP-complete languages are P-isomorphic to each other.
Andras Farago
CC BY-SA 3.0
2016-02-28T19:28:49.083Z
Then can you give an example of two NP-complete languages that are not P-isomorphic? You need to prove that there are no isomorphisms.
Zirui Wang
CC BY-SA 3.0
2016-02-29T02:31:03.110Z
@ZiruiWang No such proven example is known. If it were known, it would disprove the famous Isomorphism Conjecture. See also this earlier question: http://cstheory.stackexchange.com/questions/21264/natural-candidate-against-the-isomorphism-conjecture
Andras Farago
CC BY-SA 3.0
2016-03-03T17:59:24.587Z
suggest this all could be formalized and proven "to some degree" with good definitions. there is no formal definition yet of a "phase transition" in (T)CS even though its been studied for decades (although erdos did some early work in the area); but presumably a lot of literature/ formalism in physics could be borrowed & be applicable & built on. also, phase transitions seem to have strong topological aspects. try [chat] :) ... also agree the semifamous isomorphism conjecture of berman-hartmanis is relevant.
vzn
CC BY-SA 3.0
2016-04-08T15:58:46.150Z
@AndrasFarago Since all known NP-complete problems are polynomially isomorphic to each other, you are asking whether any two (known) NP-complete problems exhibit phase transition together. But since we know that some problem does, you are asking whether all NP-complete languages exhibit phase transition.
Zirui Wang
<cc.complexity-theory><np><np-complete><phase-transition>
Does p-isomorphism preserve phase transition?
Andras Farago
# Does p-isomorphism preserve phase transition?

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

Consider two NP-complete languages that are polynomial-time isomorphic. If we know that one of them exhibits phase transition (with respect to some order parameter), does this imply that the other must also have phase transition, with respect to some (possibly different) order parameter?

Intuitively, I would expect that the answer is yes. The reason is that p-isomorphmism means that the two languages are "essentially the same," apart from a polynomial-time re-encoding. It would appear quite surprising if one of them has phase transition, while the other does not, despite their p-isomorphism. But how can the implication be proved formally?

**Tags:** cc.complexity-theory, np, np-complete, phase-transition
> **Comments:**
> **username_1**: Can you give an example of a P-time isomorphism between two NP-complete languages?  
> **username_0**: @ZiruiWang A very simple example is between Max Clique and and Max Independent Set. But there are many more (infinitely many), since it is known that all paddable NP-complete languages are P-isomorphic to each other.  
> **username_1**: Then can you give an example of two NP-complete languages that are not P-isomorphic? You need to prove that there are no isomorphisms.  
> **username_0**: @ZiruiWang No such proven example is known. If it were known, it would disprove the famous Isomorphism Conjecture. See also this earlier question: http://cstheory.stackexchange.com/questions/21264/natural-candidate-against-the-isomorphism-conjecture  
> **username_2**: suggest this all could be formalized and proven "to some degree" with good definitions. there is no formal definition yet of a "phase transition" in (T)CS even though its been studied for decades (although erdos did some early work in the area); but presumably a lot of literature/ formalism in physics could be borrowed & be applicable & built on. also, phase transitions seem to have strong topological aspects. try [chat] :) ... also agree the semifamous isomorphism conjecture of berman-hartmanis is relevant.  
> **username_1**: @AndrasFarago Since all known NP-complete problems are polynomially isomorphic to each other, you are asking whether any two (known) NP-complete problems exhibit phase transition together. But since we know that some problem does, you are asking whether all NP-complete languages exhibit phase transition.  

---

## 1 answers

### Answer by username_3 on 2016-02-29. Score: 8 | Accepted answer

Yes, but I'm not sure it means much. Yes in a trivial way: suppose $\varphi$ is an isomorphism between two $\mathsf{NP}$-complete languages $L\_1, L\_2$, and $L\_1$ exhibits a phase transition with respect to some parameter $m(x)$. Then so does $L\_2$, with respect to the parameter $m\_2(y) := m(\varphi^{-1}(y))$. (This relies on the fact that "phase transition" talks about the fraction of satisfiable instances jumping from 0 to 1, as a fraction of an exponential number of instances of a given size, and p-isomorphisms preserve densities up to a polynomial.)

I'm not sure this is such a meaningful statement, however, because the parameter $m\_2$ above can be totally unnatural from the point of view of $L\_2$. Most phase transitions of interest are with respect to some natural parameter (e.g. clause-to-variable ratio in k-SAT, density of a graph, etc.). But those natural parameters are defined in terms of some "internal" structure to the instances, not by just treating the problem instances as abstract strings in $\Sigma^\*$ ($\Sigma$ your finite alphabet). But p-isomorphism *does* just treat inputs as abstract strings, and "knows nothing" about the internal structure that we like to impose on them. So, sure, you can say that all paddable languages have a phase transition since k-SAT does. But that doesn't tell you if, for example, solvability of quadratic Diophantine equations exhibits a phase transition in terms of any parameter that is natural from the point of view of Diophantine equations...

> **Comments:**
> **username_0**: Thank you, the answer is formally correct, but I realized that I did not phrase the question well enough to express what I am really interested in. It is this: if $L_1$ exhibits phase transition within the set of $n$-bit instances (for any $n$), does this imply that $L_2$ also exhibits phase transition in the same sense? Note that the mapping $m_2(y) := m(\varphi^{-1}(y))$ of the order parameter may not imply it, because it may map n-bit instances to instances of varying length. Therefore, it is not clear if $L_2$ has phase transition for  instances of length n.  
> **username_3**: Okay. Are you sure that's what you want to ask? Length is not preserved by p-isomorphism except up to polynomials. And, under the standard encoding of k-SAT, the phase transition in k-SAT is *not* among instances of the same length. Of course, you can use a different encoding, such as saying that all n-variable instances of k-SAT will be strings of length $2^k \binom{n}{k}$ (or whatever the exact right number is) indicating which clauses are present, but that's not exactly a natural encoding. Note that these two encodings are p-isomorphic, however.  
> **username_0**: Well, I guess, I still did not phrase the question right. What I have in mind is shown by this example: fix some parameter, such as the number of vertices in a graph, and vary another parameter, such as the number of edges. Depending on the encoding, this indeed may not mean that we stay within the set of strings of the same length. Now, if we know that a graph property has phase transition according to this order parameter (the density of the graph), does this imply that another language, describing another graph property, preserves phase transition, if the languages are P-isomorphic?  
> **username_3**: @AndrasFarago: Okay, excellent. But now I think a small variant of my answer still gives a positive-but-kind-of-trivial answer: let $n(x)$ be the number of vertices of the graph $x$, and $d(x)$ the density of edges. Let $L$ be your favorite NPC language with a phase transition in $d$ ("relative to" $n$, as you describe). Let $L'$ be p-isomorphic to $L$ via $\varphi$. Then $L'$ exhibits a phase transition in $d(\varphi(x))$ "relative to" $n(\varphi(x))$.  
> **username_4**: I think what Andras wants to know is the following (please correct me if I am wrong). Lets say you have an NP-Complete problem A with a phase-transition at density x, where x is in between (0-1). Then he wants to map that problem to some other NP-Complete problem B with a phase transition at density y. The question is does the instances at density x for problem A correspond to the instances at density y for problem B. Is it 1-1?  
> **username_0**: @JoshuaGrochow The problem is that after the mapping we get a different type of phase transition, because both the parameter $d$, and the "base" $n$ are transformed. What I would like to know is this: If $L_1$ has a phase transition in $d$ "relative to" $n$, and $L_1, L_2$ are p-isomorphic, does this imply that $L_2$ also has a phase transition in some (possibly transformed) parameter $d'$, but still relative to the _same_ base $n$?  
> **username_3**: @AndrasFarago: But what do you mean by two different languages having the same base? That is, if $L_1$ is a graph problem where $n(x)$ is the number of vertices, and $L_2$ is an arbitrary subset of $\Sigma^*$ that is isomorphic to $L_1$, then what do you mean by "the same n" for $L_2$? Or do you have in mind that $L_1$ and $L_2$ are both natural graph problems that you know to be isomorphic? If the latter, one would have to examine the isomorphism to see if it preserved n; that seems very unlikely to me though, given the BH construction.  
> **username_0**: @JoshuaGrochow The "same base" I originally had in mind was simply the instance size, regardless to whether it is a graph problem or not. If $L_1$ is a language that has phase transition over $n$-bit strings, according to some order parameter $d$, does this imply that a p-isomorphic $L_2$ also has phase transition over $n$-bit strings, according to some order parameter $d'$? (Let us assume an encoding that keeps the instance length constant for varying order parameter.)  
> **username_3**: @AndrasFarago: I'm not sure that string length is particularly privileged as an example function "n" when talking about p-isomorphisms. I think my answer and previous comments essentially already addressed this: it is unlikely to be true, since p-isomorphism only preserves length up to polynomials, and the only way I see to transfer an order parameter $d$ across a p-isomorphism is as above (that is, $d(\varphi(y))$).  

---

