Referência perguntando: transição de fase em SAT

Question

Esta não é uma questão técnica, espero que esta comunidade tenha uma sala para essas perguntas, mas vou deletar no caso de isso ser inadequado.

foi experimentalmente observado (por exemplo, aqui ) que ao escolher um $ 3 $ -sat fmula pelo seguinte processo:

na entrada $ (n \ alpha n) $ : escolha $ \ Alpha N $ cláusulas uniformemente aleatoriamente do conjunto de todas as cláusulas de $ 3 $ literais sobre $ x_1, \ ldots, x_n $ e devolver a conjunção dessas cláusulas.

A probabilidade de que a fórmula de saída seja satisfatória depende da $ \ alfa $ : se $ \ alfa \ ll c $ A probabilidade é muito próxima de $ 1 $ , e se $ \ alpha \ gg c $ A probabilidade é muito próxima de $ 0 $ (foi observado para uma classe geral $ K $ instâncias -sat ).

Minha pergunta é qual é a compreensão teórica desse problema? Para o melhor do meu conhecimento, por outros problemas é possível provar sinistros semelhantes facilmente (por exemplo, a probabilidade de que um gráfico aleatório $ g (n, p) $ Um clique de tamanho $ 4 $ é quase $ 1 $ quando $ p (n)= ímama (n ^ {- 2/3}) $ e é quase $ 0 $ quando $ p (n)= o (n ^ {- 2/3}) $ , e pode ser comprovado por um uso básico de segundos momentos).

No entanto, para SAT, eu não poderia encontrar provas. Você conhece algum progresso neste problema?

Answer 1

Os dois resultados rigorosos mais relevantes são:

.
1. ehud friedgut, Limites afiados de propriedades do gráfico e a $ k $ -sat problema . Este artigo (com um apêndice por Jean Bourgain) mostra que $ k $ -sat exibe um limiar afiado. No entanto, um priori este limiar pode depender da $ n $ (isto é, este método não pode mostrar que $ \ alfa $ é constante).
2. Jian Ding, Allan Sly, Nike Sun, Prova da Conjectura de Satisfação para Grande $ k $ . Os autores determinam o valor exato da $ \ alfa $ para $ k \ geq k_0 $ . Este valor de $ \ alfa $ tinha sido calculado por físicos usando o método da cavidade, mas seus argumentos não são rigorosos.

O trabalho relacionado discute a geometria do espaço da solução da $ k $ -sat em torno de vários limites. Ver por exemplo, Dimitris Achlioptas, Amin Coja-Oglan, Federico Ricci-Tersenghi, no geometria de espaço de solução de problemas de satisfação aleatória .