5
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • $\begingroup$ Can you give an example of a P-time isomorphism between two NP-complete languages? $\endgroup$
    – Zirui Wang
    Feb 28, 2016 at 18:12
  • 1
    $\begingroup$ @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. $\endgroup$
    – Andras Farago
    Feb 28, 2016 at 19:16
  • $\begingroup$ 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. $\endgroup$
    – Zirui Wang
    Feb 28, 2016 at 19:28
  • 4
    $\begingroup$ @ZiruiWang No such proven example is known. If it were known, it would disprove the famous Isomorphism Conjecture. See also this earlier question: cstheory.stackexchange.com/questions/21264/… $\endgroup$
    – Andras Farago
    Feb 29, 2016 at 2:31
  • $\begingroup$ 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 Theoretical Computer Science Chat :) ... also agree the semifamous isomorphism conjecture of berman-hartmanis is relevant. $\endgroup$
    – vzn
    Mar 3, 2016 at 17:59

1 Answer 1

Reset to default
8
$\begingroup$

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...

Improve this answer
$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – Andras Farago
    Feb 29, 2016 at 20:39
  • $\begingroup$ 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. $\endgroup$
    – Joshua Grochow
    Feb 29, 2016 at 21:18
  • $\begingroup$ 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? $\endgroup$
    – Andras Farago
    Feb 29, 2016 at 23:58
  • $\begingroup$ @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))$. $\endgroup$
    – Joshua Grochow
    Mar 1, 2016 at 0:36
  • $\begingroup$ 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? $\endgroup$
    – Tayfun Pay
    Mar 1, 2016 at 6:12

Your Answer

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

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