参考询问：SAT中的阶段过渡

Question

这不是一个技术问题，我希望这个社区有一个房间的这些问题，但我会删除它，以防万一这是不合适的。

它已被实验观察（例如这里）在选择 $ 3 $ -sat公式时：

在输入 $（n，\ alpha n）$ ：选择 $ \ alpha n $ 条文从 $ 3 $ 文字的所有条款中的所有子句随机均匀， $ x_1，\ ldots，x_n $ ，并返回这些条款的结合。

输出公式满足的概率取决于 $ \ alpha $ ：if $ \ alpha \ ll c $ 概率非常接近 $ 1 $ ，如果 $ \ alpha \ gg c $ 概率非常接近 $ 0 $ （它已被录音为 $ k $ -sat实例）。

我的问题是对这个问题的理论理解是什么？据我所知，对于其他问题，可以很容易证明类似的声明（例如随机图 $ g（n，p）$ 的概率一个大小的clique $ 4 $ 几乎 $ 1 $ 当 $ p（n）=oomega（n ^ {-2/3}）$ ，几乎 $ 0 $ 当 $ p（n）= o（n ^ { - 2/3}）$ ，可以通过第二矩的基本使用来证明它）。

然而，对于坐着，我可以找到证明。你知道这个问题的任何进展吗？

Answer 1

两个最相关的严格结果是：

1. ehud friedgut，锐利的图形属性阈值， $ k $ -sat问题。本文（Jean Bourgain的附录）显示<跨度类=“Math-Container”> $ k $ -sat展示了一个尖锐的阈值。但是，此阈值的先验可能取决于 $ n $ （即，此方法不能显示 $ \ alpha $ 是常数）。
2. 剑丁，艾伦狡猾，耐克太阳，宽大 $ k $ 。作者确定 $ \ alpha $ 的确切值为 $ k \ geq k_0 $ 。 $ \ alpha $ 的这个值由物理学家使用腔方法计算，但它们的争论并不严格。

相关工作讨论了 $ k $ -sat周围的解决方案空间的几何图形。查看Dimitris Achlioptas，Amin Coja-Oghlan，Federico Ricci-Tersenghi，随机约束满意度问题的解决方案空间几何形状