La Singularidad Desnuda

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

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

11 comentarios to “Transiciones de fase: una lección vital”

  1. Juanlu said

    Me encanta el paralelismo que haces al final con las situaciones de la vida y he de decir que con algún matiz de complejidad extra, estoy de acuerdo. Un buen ejemplo de transición de fase se produce en la última película que he visto “En busca de la felicidad”.

  2. Carlos said

    No la he visto aún. ¿Qué tal está?

  3. Juanlu said

    Tal vez la historia pueda parecer exagerada en algún momento pero el mensaje que transmite es conmovedor. Si alguna vez has creído en tí más de lo que lo hacía el mundo, no te dejará indiferente.

  4. JJ said

    Pero a veces a pasar de la zona difícil a la fácil hace falta un tiempo no polinómico, ¿no?

  5. Carlos said

    Bueno, si nos estamos moviendo en el espacio de instancias, dependerá del criterio que sigamos para ello. ¿O te refieres a los caminos largos en el paisaje de búsqueda?

  6. LOLA said

    SUPER ME FACINA QUIERO SABER SOBRE LOS NANODISPOSITIVOS, QUE FUNCION CUMPLEN Y DEMAS .DEVUELVANME EL MENSAJE PORFA.CHAO

  7. SUPER SUS NOTICIAS ME GUSTARIA SABER TODO SOBRE LOS NANO DISPOSITIVOS.CHAO .LOS FELICITO

  8. HOLA

  9. Quisiera manifestar que una vez leído este libro, la tecnología del siglo XX dará un salto…

    http://www.trafford.com/07-1729

  10. Carlos said

    ¿Quieres decir que una vez leído el libro se podrá viajar al siglo pasado y modificar la tecnología de entonces, o se trata de un libro del siglo XX que no ha actualizado el reclamo publicitario?

  11. El problema de la satisfacibilidad es un problema del siglo XX.

    De todas formas, diga lo que os diga ese problema, lo más importante es sobre qué maquina lo estemos ejecutando.

Sorry, the comment form is closed at this time.

 
A %d blogueros les gusta esto: