论文标题
型号RB具有较慢的生长域的确切相变
Exact Phase Transitions of Model RB with Slower-Growing Domains
论文作者
论文摘要
第二刻方法一直是下降许多随机约束满意度问题的满足性阈值的有效工具。但是，计算通常很难进行，因此，只能获得一些松散的结果。在本文中，基于一个精致的分析，该分析完全利用了第二瞬间方法的功率，我们证明随机RB实例可以在更轻松的条件下表现出精确的相位过渡，尤其是增长较慢的域大小。这些结果是使用第二幅方法的最好的结果，应引入新工具以获得任何更好的结果。
The second moment method has always been an effective tool to lower bound the satisfiability threshold of many random constraint satisfaction problems. However, the calculation is usually hard to carry out and as a result, only some loose results can be obtained. In this paper, based on a delicate analysis which fully exploit the power of the second moment method, we prove that random RB instances can exhibit exact phase transition under more relaxed conditions, especially slower-growing domain size. These results are the best by using the second moment method, and new tools should be introduced for any better results.
