O que se quer dizer com argumentos de física estatística heurística?

29

Ouvi dizer que existem argumentos heurísticos na física estatística que produzem resultados na teoria das probabilidades, para as quais provas rigorosas são desconhecidas ou muito difíceis de obter. O que é um exemplo simples de brinquedo desse fenômeno?

Seria bom se a resposta assumisse pouco conhecimento em física estatística e pudesse explicar o que são essas heurísticas misteriosas e como elas podem ser justificadas informalmente. Além disso, talvez alguém possa indicar o panorama geral de quanto dessas heurísticas pode ser rigorosamente justificada e como o programa de Lawler, Schramm e Werner se encaixa nisso.

arnab
fonte
Pedimos desculpas antecipadamente pela natureza "iniciante" desta questão!
arnab
11
Eu tinha uma pergunta semelhante - por exemplo, uma fórmula para a taxa de crescimento do número de caminhadas evitáveis ​​na rede 4d é justificada através da "abordagem de grupo de renormalização", mesmo que não exista uma prova rigorosa
Yaroslav Bulatov,
entropia máximo (a-la Jaynes e relações associadas) é um dos mais utilizados (de um modo ou outro)
Nikos M.

Respostas:

22

O segundo parágrafo da resposta do RJK merece mais detalhes.

Deixe ser uma fórmula na forma normal conjuntiva, com m, n cláusulas variáveis, e na maioria das variáveis k por cláusula. Suponha que desejamos determinar se ϕ tem uma tarefa satisfatória. A fórmula ϕ é uma instância do problema de decisão do k-SAT.ϕϕϕ

Quando existem poucas cláusulas (então m é bem pequeno comparado a n), quase sempre é possível encontrar uma solução. Um algoritmo simples encontrará uma solução em tempo aproximadamente linear no tamanho da fórmula.

Quando há muitas cláusulas (então m é bastante grande comparado a n), quase sempre ocorre que não há solução. Isso pode ser mostrado por um argumento de contagem. No entanto, durante a pesquisa, quase sempre é possível remover grandes partes do espaço de pesquisa por meio de técnicas de consistência, porque as muitas cláusulas interagem muito extensivamente. O estabelecimento da insatisfação geralmente pode ser feito com eficiência.

Em 1986, Fu e Anderson conjeturaram uma relação entre problemas de otimização e física estatística, baseada em sistemas de vidro giratório. Embora eles usassem frases como

Intuitivamente, o sistema deve ser suficientemente grande, mas é difícil ser mais específico.

eles realmente dão previsões específicas.

  • Y Fu e PW Anderson. Aplicação da mecânica estatística a problemas NP-completos na otimização combinatória , 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. Determinando a complexidade computacional a partir das características 'transições de fase' , Nature 400 133–137, 1999. ( doi: 10.1038 / 22055 , versão gratuita )

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

  • k

Dimitris Achlioptas trabalhou em muitas das questões restantes e mostrou que o argumento acima também se aplica a problemas de satisfação de restrições. Eles podem usar mais do que apenas dois valores para cada variável. Um artigo-chave mostra rigorosamente por que o algoritmo de propagação de pesquisa funciona tão bem para resolver instâncias aleatórias de k-SAT.

  • A. Braunstein, M. Mézard, R. Zecchina, Propagação da pesquisa: um algoritmo para a satisfação , Estruturas aleatórias e algoritmos 27 201–226, 2005. doi: 10.1002 / rsa.20057
  • D. Achlioptas e F. Ricci-Tersenghi, Sobre a Geometria do Espaço da Solução de Problemas Aleatórios de Satisfação de Restrições , STOC 2006, 130-139. ( pré-impressão )
András Salamon
fonte
Obrigado pelas referências! Estou aceitando esta resposta, pois é a mais abrangente. Eu ainda estaria interessado em uma descrição informal do programa de Lawler, Schramm & Werner.
arnab 17/09/10
11

Há uma pesquisa muito recente realizada por Lawler sobre os LES . Você precisará conhecer um pouco de análise complexa.

Embora não esteja diretamente relacionado à sua pergunta, talvez você possa conferir alguns dos documentos de Achlioptas, que também se enquadram sob a égide da "formalização das heurísticas dos físicos", embora do ponto de vista de um cientista da computação teórico. Ou talvez, mais profundamente na perspectiva dos statphys, você possa navegar por alguns dos trabalhos de Zecchina .

Acho que vale a pena acrescentar que o que você chamou de "resultados" dos físicos - a maioria dos quais deveria ser chamado de conjecturas - nessa categoria muito ampla de problemas depende quase tanto (ou até mais) de experimentos numéricos quanto ( que) em argumentos heurísticos.

RJK
fonte
Obrigado pelo link para a pesquisa! Você pode expandir mais sobre o que são esses experimentos computacionais? Quais insights da física estatística são usados? Eu estava procurando por um exemplo simples de brinquedo (digamos, da teoria da percolação) em que alguém pudesse informalmente fazer um argumento estatístico baseado na física.
arnab 12/09
basicamente, Monte Carlo / experimentos estatísticos, que também são utilizados intensamente no estudo de sab e ter crosspollinated fortemente com a direcção da teoria na área
vzn
2

(expnanding no meu comentário)

NP

Uma pesquisa sobre " heurísticas da natureza " pode ser encontrada aqui (cerca de 95)

Outras heurísticas envolvem langrangianos generalizados (também conhecidos como algoritmos primal-dual / de expectativa-maximização)

No entanto, eles não esgotam todas as " heurísticas da natureza ", pois, a partir de 2003, novas heurísticas baseadas no eletromargnetismo foram usadas para lidar com métodos de otimização contínua e discreta / combinatória (como a mochila multidimensional ou o TSP , por volta de 2012)

Nikos M.
fonte