¿Qué se entiende por argumentos heurísticos de física estadística?

29

He escuchado que existen argumentos heurísticos en física estadística que arrojan resultados en la teoría de probabilidad para la cual se desconocen o son muy difíciles las pruebas rigurosas. ¿Cuál es un ejemplo de juguete simple de tal fenómeno?

Sería bueno si la respuesta asumiera pocos antecedentes en física estadística y pudiera explicar cuáles son estas misteriosas heurísticas y cómo pueden justificarse informalmente. Además, tal vez alguien pueda indicar el panorama general de cuánto de estas heurísticas se puede justificar rigurosamente y cómo el programa de Lawler, Schramm y Werner encaja en esto.

arnab
fuente
¡Disculpas de antemano por la naturaleza 'principiante' de esta pregunta!
arnab
1
Tuve una pregunta similar, por ejemplo, una fórmula para la tasa de crecimiento del número de caminatas autoevitantes en celosía 4d se justifica a través del "enfoque de grupo de renormalización" a pesar de que no hay pruebas rigurosas
Yaroslav Bulatov
la entropía máxima (a-la Jaynes y las relaciones asociadas) es una de las más utilizadas (de una forma u otra)
Nikos M.

Respuestas:

22

El segundo párrafo de la respuesta de RJK merece más detalles.

Vamos ser una fórmula en forma normal conjuntiva, con m cláusulas, n variables, y en la mayoría de k variables por cláusula. Supongamos que queremos determinar si ϕ tiene una asignación satisfactoria. La fórmula ϕ es una instancia del problema de decisión k-SAT.ϕϕϕ

Cuando hay pocas cláusulas (por lo que m es bastante pequeño en comparación con n), casi siempre es posible encontrar una solución. Un algoritmo simple encontrará una solución en un tiempo aproximadamente lineal en el tamaño de la fórmula.

Cuando hay muchas cláusulas (por lo que m es bastante grande en comparación con n), casi siempre ocurre que no hay solución. Esto se puede mostrar mediante un argumento de conteo. Sin embargo, durante la búsqueda, casi siempre es posible podar grandes partes del espacio de búsqueda mediante técnicas de coherencia, ya que las numerosas cláusulas interactúan de manera muy extensa. El establecimiento de la insatisfacción generalmente se puede hacer de manera eficiente.

En 1986, Fu y Anderson conjeturaron una relación entre los problemas de optimización y la física estadística, basada en sistemas de vidrio giratorio. Aunque usaban oraciones como

Intuitivamente, el sistema debe ser lo suficientemente grande, pero es difícil ser más específico.

en realidad dan predicciones específicas.

  • Y Fu y PW Anderson. Aplicación de la mecánica estadística a problemas NP-completos en optimización combinatoria , J. Phys. A. 19 1605, 1986. doi: 10.1088 / 0305-4470 / 19/9/033

α=m/n

  • Rémi Monasson, Riccardo Zecchina, Scott Kirkpatrick, Bart Selman, Lidror Troyansky. Determinación de la complejidad computacional a partir de las características 'transiciones de fase' , Nature 400 133-137, 1999. ( doi: 10.1038 / 22055 , versión gratuita )

α1<α2αα1αα2ϕ

  • k

Dimitris Achlioptas trabajó en muchos de los problemas restantes y demostró que el argumento anterior también es válido para problemas de satisfacción de restricciones. Estos pueden usar más de dos valores para cada variable. Un artículo clave muestra rigurosamente por qué el algoritmo de Propagación de encuestas funciona tan bien para resolver instancias de k-SAT aleatorias.

  • A. Braunstein, M. Mézard, R. Zecchina, Propagación de encuestas: un algoritmo para la satisfacción , estructuras aleatorias y algoritmos 27 201–226, 2005. doi: 10.1002 / rsa.20057
  • D. Achlioptas y F. Ricci-Tersenghi, Sobre la geometría de la solución espacial de los problemas de satisfacción de restricciones aleatorias , STOC 2006, 130–139. ( preimpresión )
András Salamon
fuente
Gracias por las referencias! Estoy aceptando esta respuesta ya que es la más completa. Sin embargo, todavía estaría interesado en una descripción informal del programa de Lawler, Schramm y Werner.
arnab
11

Hay una encuesta muy reciente realizada por Lawler sobre SLE . Necesitará conocer un poco de análisis complejo.

Aunque no está directamente relacionado con su pregunta, tal vez podría consultar algunos de los artículos de Achlioptas que también caben bajo el paraguas de "formalizar la heurística de los físicos", aunque desde el punto de vista de un informático teórico. O tal vez más profundamente en la perspectiva de statphys podría navegar a través de algunos de los trabajos de Zecchina .

Creo que vale la pena agregar que lo que ustedes han denominado "resultados" de los físicos, la mayoría de los cuales deberían llamarse conjeturas, en esta categoría muy amplia de problemas dependen casi tanto (o incluso más) de experimentos numéricos como ( que) sobre argumentos heurísticos.

RJK
fuente
Gracias por el enlace a la encuesta! ¿Puedes ampliar más sobre qué son estos experimentos computacionales? ¿Qué ideas de la física estadística se utilizan? Estaba buscando un ejemplo simple de juguete (digamos, de la teoría de la filtración) en el que uno podría hacer informalmente un argumento basado en la física estadística.
arnab
Básicamente, los experimentos de Monte Carlo / estadística, que también se usan mucho en el estudio de SAT y se han cruzado en gran medida con la dirección de la teoría en el área
vzn
2

(expirando en mi comentario)

NP

Una encuesta de " heurística de la naturaleza " se puede encontrar aquí (circa 95)

Otras heurísticas involucran a los langrangianos generalizados (también conocidos como algoritmos primarios-duales / de maximización de expectativas)

Sin embargo, estos no agotan todas las " heurísticas de la naturaleza " ya que, de hecho, desde 2003 en adelante, se han utilizado nuevas heurísticas basadas en el electromargnetismo para abordar los métodos de optimización continua y discreta / combinatoria (como la mochila multidimensional o el TSP , alrededor del año 2012)

Nikos M.
fuente