随机3-SAT命中时间的线性方差
Linear Variance of the Random 3-SAT Hitting Time
OpenAI 数学仓库收录的研究手稿。展开查看英文摘要，或标记后让我进一步解释。
具体内容
该稿件研究随机3-SAT的不可满足前缀出现时间，即命中时间。摘要表示，在n个布尔变量、子句由三个不同变量独立均匀带符号且有放回抽样生成时，首个不可满足前缀的方差为Θ(n)。上界去掉了此前方差估计中的对数损失，匹配下界由Wilson的转移宽度定理得到。该手稿为AI产生，未经独立审查或同行评议，结论应视为作者声称。
- 研究随机3-SAT首个不可满足前缀的方差，作者声称其为Θ(n)。
- 上界消除此前估计中的对数损失，下界由Wilson转移宽度定理给出。
- 模型为n个变量、三个不同变量独立均匀带符号且有放回抽样的子句。
AI 产生的研究手稿；收录不表示已完成独立审查或同行评议。
英文原始摘要
For random 3-SAT on n Boolean variables, with independent uniformly signed clauses on three distinct variables sampled with replacement, we prove that the first unsatisfiable prefix has variance $`\Theta(n)`$. The upper bound removes the logarithmic loss in the earlier variance estimate; the matching lower bound follows from Wilson's transition-width theorem.
用户标记：未标记
固定编号：585bceb69f1873ae
原文来源