La Singularidad Desnuda

Un universo impredecible de pensamientos y cavilaciones sobre ciencia, tecnología y otros conundros

Posts Tagged ‘Transición de Fase’

Transiciones de fase: una lección vital

Posted by Carlos en febrero 7, 2007

El término científico transición de fase es muy interesante. Una transición de fase en un sistema indica un cambio brusco en sus propiedades al sobrepasar cierto valor crítico en alguna variable de control del mismo. Los ejemplos más habituales nos los encontramos en física. Consideremos por ejemplo el agua. A temperatura ambiente es líquida, pero si reducimos la temperatura por debajo de 0ºC se congela y pasa a ser sólida. Este cambio es brusco, esto es, el agua no empieza a espesarse, convirtiéndose en una especie de melaza cada vez más consistente a medida que baja la temperatura, sino que cristaliza rápidamente, en lo que se tarda en alcanzar el equilibrio térmico entre diferentes partes del líquido. Otro tanto podemos conseguir jugando por ejemplo con la presión del líquido en lugar de con la temperatura. Matemáticamente, podríamos decir que se produce una discontinuidad en las propiedades del sistema al pasar de una fase a otra, típicamente por haber alguna singularidad en alguna de dichas propiedades o en sus derivadas.

El fenómeno de las transiciones de fase no es particular de la física ni mucho menos. Son muy frecuentes por ejemplo en el área de la matemática discreta, y en particular en teoría de grafos o en optimización combinatoria. Podemos considerar un ejemplo bien simple: el problema de la sastisfacibilidad lógica (SAT). Imaginemos que tenemos una fórmula lógica, e.g., (x1 or ~x2 or ~x3) and (x1 or x2 or x4). Esta fórmula lógica está expresada en forma normal conjuntiva, es decir, tenemos un conjunto de cláusulas unidas por la conectiva and, cada una de las cuales es un conjunto de literales (variables lógicas o su negación, que pueden tomar un valor verdadero o falso) unidos por la conectiva or. El problema consiste en determinar si existe una asignación de valores (verdadero o falso) a las variables lógicas de manera que la fórmula sea cierta (i.e., que todas las cláusulas sean ciertas). En el ejemplo anterior, cualquier asignación que incluya x1 = verdadero valdría (no sería ésta la única solución en este ejemplo).

Puede parecer que no es difícil determinar si una fórmula lógica es satisfacible o no, y la verdad es que en la práctica esto es cierto. Por supuesto, si el número de variables crece mucho, el problema se hace pesado, pero no inherentemente difícil. De hecho, hay algoritmos que son capaces de resolver rápidamente el problema para miles de variables. A pesar de esto, el problema SAT es el ejemplo paradigmático de la clase de problemas NP: dada una fórmula arbitraria, en el peor caso no existe ningún algoritmo conocido que demuestre su satisfacibilidad o insatisfacibilidad en tiempo polinomial en el tamaño del problema (esto es, si el tamaño es n, en tiempo acotado por nc, donde c es una constante). ¿Cómo es eso posible en este problema? Pues porque hay una transición de fase de por medio.

Analicemos el problema para un número de variables fijo, en función del número de cláusulas que tiene. Si este número es muy pequeño, el problema será muy probablemente satisfacible, ya que tenemos muchos grados de libertad (variables cuyos valores podemos fijar), y pocas restricciones (cláusulas). Por el contrario, si el número de cláusulas es muy alto, la sitación es la inversa, y el problema es muy probablemente no satisfacible. ¿Que ocurre con valores intermedios? Ahí está lo interesante. Una instancia cualquiera del problema sigue siendo con probabilidad cercana a 1.0 satisfacible aunque aumentemos el número de cláusulas, hasta que llegamos a una relación entre el número de cláusulas y el número de variables de entre 4 y 5 cláusulas por variable. Ahí se pasa rápidamente a instancias que son insatisfacibles con probabilidad cercana a 1.0. El punto crítico está en aproximadamente de 4.24 cláusulas por variable (suponiendo siempre que cada cláusula tiene 3 literales). Una instancia situada ahí es prácticamente satisfacible/insatisfacible con el 50% de probabilidad.

SAT probability of satisfiability

La imagen superior está tomada de un trabajo clásico de D. Mitchell, B. Selman, y H. Levesque, publicado en la décima conferencia de la American Association for Artificial Intelligence, y titulado:

La resolución del problema es muy fácil en general, ya que un algoritmo especializado se da cuenta enseguida de si hay solución o no, salvo cuando estamos en la zona en la que se produce la transición de fase. En ella, la eficiencia de los algoritmos de resolución es enormemente limitada, y se ven obligados a explorar una cantidad significativa (no polinomial) de las posibles soluciones al problema. Se habla en este caso de una transición de fase fácil-difícil-fácil, ya que a medida que nos desplazamos por el eje X visitamos fugazmente una zona de dificultad entre dos amplias regiones de fácil resolución.

La belleza de este tipo de fenómenos está en lo que aprendemos de ellos, y luego podemos aplicar a nosotros mismos. En numerosas ocasiones nuestra vida experimentará transiciones de fase y zonas de extrema complejidad, pero uno debe pensar que tras el pico de dificultad, nos adentraremos de nuevo en la región fácilmente resoluble. Al menos, eso pienso yo.

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Anuncios

Posted in Física, Matemáticas, Optimización Combinatoria, Singularidad | Etiquetado: , , , | 11 Comments »