"Cambio de fase" de una puramente matemático del sistema

Question

Cada tan a menudo oigo a la gente hablar sobre "transiciones de fase" en puramente matemática o computación contextos, donde no hay física en la vista. Hoy, por ejemplo, he escuchado a algunas personas hablando sobre "transiciones de fase" cuando colorear los bordes de grafos aleatorios.

Se trata simplemente de una simple reutilización de la física de plazo, o es que hay un más general el concepto matemático de un "cambio de fase", de los cuales físico de los cambios de fase son un ejemplo? Si es así, ¿cuáles son algunos ilustrativos puramente matemático/físico ejemplos?

Answer 1

No tengo la reputación de publicar un comentario, pero ...

"Donde los Problemas Realmente difíciles que Se" hace una crítica de error relativo a donde los problemas realmente difíciles.

Problemas en el estrecho "región de la frontera" puede ser fácilmente trasladado a la "más restringido de la región" mediante la adición de n variables nuevas y 6n de nuevas cláusulas. Estas cláusulas sólo necesitan involucrar a aquellos que n varaibles, pero no es necesario. Este es un polinomio de transformación que no tiene ningún efecto sobre la solución al problema original.

Me gustaría sugerir que el uso de "cambio de fase" en este contexto podría ser incorrecta.

Answer 2

En Donde la Realidad de los Problemas Duros Son el concepto de cambio de fase en NP completo de los problemas que se discute. Tiene el sentido de una estrecha región de la frontera de la física, pero no del todo el sentido de la fijación de las cosas (como la temperatura de fusión de la solución).

Answer 3

El ejemplo más común lo que puedo pensar es al azar en la teoría de grafos, que sirve como el modelo matemático de todo tipo de redes, donde una brusca transición se produce entre los desconectado régimen y el conectado régimen cuando la probabilidad de la existencia de una arista entre dos nodos supera $\log n/n$ donde $n$ es el número de nodos (vértices). Si una llamada a la que un "cambio de fase" es un abuso, entonces que así sea.