基準尋問：SATにおける相転移

Question

これは技術的な質問ではありません、私はこのコミュニティがそのような質問の余地があることを願っていますが、これが不適切である場合には削除します。

それは実験的に観察されました（例えばここでは、次のプロセスで $ 3 $ -sat式を選択するとき：

入力 $（n、\ alpha n）$ ： $ \ alpha n $ 句を選択します。 $ 3 $ リテラルのすべての句のセットから均一にランダムに均一に $ x_1、\ ldots、x_n $ そして、これらの句の接続詞を返します。

出力された式が満足できる確率は、 $ \ alpha $ によって異なります。 $ \ alpha \ ll c $ 確率は $ 1 $ に非常に近いです。 $ \ alpha \ gg c $ 確率は $ 0 $ に非常に近いです（一般的な $ k $ -satインスタンスについて観察されました。 ）

私の質問はこの問題の理論的な理解は何ですか？私の知る限りでは、他の問題のために、同様の主張を非常に簡単に証明することが可能である（例えば、ランダムグラフ $ g（n、p）$ x / span>が持っている可能性があります）。サイズ $ 4 $ のクリークは、 $の場合、ほぼ $ 1 $ です。 p（n）=omega（n ^ { - 2/3}）$ 、ほとんど $ p（n）= o（n ^ { - 2/3}）$ 、そしてそれは2番目のモーメントの基本的な使用によって証明されることができます）。

しかし、座席私は証明を見つけることができました。あなたはこの問題の進歩を知っていますか？

Answer 1

最も関連のある2つの厳密な結果は次のとおりです。

1. Ehud Friedgut、グラフプロパティの鋭いしきい値、およびspan class=" math-container "> $ k $ -sat問題。この論文（Jean Bourgainによる付録付）は、 $ k $ -satが鋭いしきい値を示します。ただし、このしきい値は $ n $ に依存できます（つまり、このメソッドは $ \ alpha $ は定数です）。
2. Jian Ding、アラン・スリー、ナイキ・サン、 real="nofollow noreferrer">大きい $ k $ 。著者らは、 $ \ alpha $ の正確な値を決定します。 $ k \ geq k_0 $ 。 $ \ alpha $ のこの値は、キャビティ法を使用して物理学者によって計算されましたが、それらの引数は厳密ではありません。

関連作業では、 $ k $ -satの解決スペースのジオメトリについて、さまざまなしきい値について説明します。例えばDimitris Achlioptas、Amin Coja-Oghlan、Federico Ricci-Tersenghi、ランダム制約満足度問題の解決策幾何学的形状