Richiesta di riferimento: Transizione di fase in SAT

Question

Questa non è una domanda tecnica, spero che questa comunità abbia una stanza per tali domande, ma lo cancellerò nel caso in cui questo sia inappropriato.

è stato sperimentalmente osservato (ad es. Qui ) che quando si sceglie una $ 3 $ -Sat formula dal seguente processo:

on input $ (n, \ alfa n) $ : selezionare $ \ alfa n $ clausole uniformemente a caso dal set di tutte le clausole di $ 3 $ letterali sopra $ x_1, \ ldots, x_n $ e restituire la congiunzione di queste clausole.

La probabilità che la formula outpdata sia soddisfatta dipende da $ \ alfa $ : se $ \ alpha \ ll c $ La probabilità è molto vicina a $ 1 $ e se $ \ alfa \ gg c $ La probabilità è molto vicina a $ 0 $ (è stato osservato per un General $ k $ -SAT ).

La mia domanda è qual è la comprensione teorica di questo problema? Per quanto ne so, per altri problemi è possibile dimostrare di rivendicazioni simili abbastanza facilmente (ad esempio la probabilità che un grafico casuale $ g (n, p) $ ha una cricca di dimensioni $ 4 $ è quasi $ 1 $ quando $ P (n)=omega (n ^ {- 2/3}) $ ed è quasi $ 0 $ quando $ P (n)= o (n ^ {- 2/3}) $ , e può essere dimostrato da un uso di base dei secondi momenti).

Tuttavia, per Sat I non riuscivo a trovare le prove. Conoscete qualche progresso in questo problema?

Answer 1

I due risultati rigorosi più rilevanti sono:

.
1. ehud friedgut, soglie taglienti delle proprietà del grafico e la $ k $ -Sat problema . Questo documento (con un'appendice di Jean Bourgain) mostra che $ k $ -sat esibisce una soglia tagliente. Tuttavia, a priori questa soglia potrebbe dipendere da $ N $ (cioè, questo metodo non può mostrare che $ \ alfa $ è costante).
2. Jian Ding, Allan Sly, Nike Sun, Prova del congettura della soddisfattiva per la matematica di grandi dimensioni Contenitore "> $ k $ . Gli autori determinano il valore esatto della classe $ \ alfa $ per $ k \ geq k_0 $ . Questo valore di $ \ alfa $ era stato calcolato dai fisici che utilizzano il metodo di cavità, ma i loro argomenti non sono rigorosi.

Il lavoro correlato discute la geometria dello spazio della soluzione di $ k $ -Sat intorno a varie soglie. Vedere Ad esempio Dimitris Achlioptas, Amin Coja-Oghlan, Federico Ricci-tersenghi, sul Geometria spaziale soluzione di problemi di soddisfazione del vincolo casuale .