Un valor crítico de un parámetro de control (como densidad de cláusulas, probabilidad de arista o densidad de restricciones) en el que una familia de instancias lógicas o combinatorias aleatorias exhibe un cambio abrupto en el comportamiento típico —por ejemplo, un cambio brusco de satisfactible a insatisfactible con alta probabilidad cuando el tamaño del sistema tiende a infinito.

Principio

Las transiciones de fase surgen de restricciones combinatorias colectivas: cuando un parámetro de control cruza un umbral, el espacio de soluciones experimenta un cambio estructural (agrupamiento, condensación, desaparición de soluciones) que produce diferencias macroscópicas en propiedades típicas y en la accesibilidad algorítmica.

Demostración

Ejemplo canónico: el k-SAT aleatorio presenta una razón cláusulas/variables r_k umbral tal que por debajo de r_k las fórmulas suelen ser satisfactibles y por encima suelen ser insatisfactibles; resultados empíricos y rigurosos identifican valores aproximados y a veces muestran umbrales nítidos en el límite de muchas variables.

Aplicación incorrecta

Tratar fluctuaciones por tamaño finito o degradaciones en el rendimiento dependientes del algoritmo como verdaderas transiciones de fase, o suponer que cada familia paramétrica tiene un único umbral nítido en lugar de posibles transiciones múltiples o cruces graduales.

Consecuencia

Identificar puntos de transición de fase guía los análisis de dureza en promedio, predice los regímenes algorítmicos donde los solvers fallan o triunfan, y conecta fenómenos combinatorios con conceptos de física estadística empleados para desarrollar heurísticas y pruebas.

Inversión

En vez de centrarse en el parámetro crítico donde cambia el comportamiento, puede estudiarse por separado los regímenes subcrítico y supercrítico para clasificar la geometría del espacio de soluciones y las estrategias algorítmicas en lugar del único punto de transición.

Límite

Los puntos de transición de fase se definen respecto de un ensemble específico y un régimen asintótico; pueden no manifestarse a tamaños pequeños, depender de la especificación del modelo y no implicar una criticidad tipo física universal en cada ensemble lógico.

Tensión semántica

Existe tensión entre las analogías con transiciones de fase físicas (exponentes críticos, universalidad) y los umbrales combinatorios que pueden carecer de parámetros continuos o límites termodinámicos; el vocabulario coincide, pero el contenido matemático puede diferir sustancialmente.

Síntesis

Un punto de transición de fase es el parámetro crítico en un conjunto de instancias lógicas aleatorias donde la estructura típica de soluciones sufre un cambio cualitativo; comprender dicho punto y los regímenes adyacentes explica la dureza empírica, orienta el diseño algorítmico y vincula la combinatoria con la intuición de la física estadística.