Random k-Sat: A Tight Threshold For Moderately Growing k期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

Random k-Sat: A Tight Threshold For Moderately Growing k

Authors:

Institution:

(1) Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA;(2) Department of Mathematics and Statistics, University of Melbourne, VIC 3010, Australia;(3) Present address: Canada Research Chair in Combinatorics and Optimization, Department of Combinatorics and Optimization, University of Waterloo, Waterloo ON, N2L 3G1, Canada

Abstract:

We consider a random instance I of k-SAT with n variables and m clauses, where k=k(n) satisfies k—log₂ n rarr

. Let m ₀=2^k nln2 and let isin

(n)>0 be such that isin

. We prove that

${}^{{\lim }}_{{n \to \infty }} \Pr {\left( {I{\text{is}}{\text{satisfiable}}} \right)} = \left\{ {^{{1m \leqslant {\left( {1 - \in } \right)}m_{0} }}_{{0m \geqslant {\left( {1 + \in } \right)}m_{0} }} .} \right.$

* Supported in part by NSF grant CCR-9818411. dagger

Research supported in part by the Australian Research Council and in part by Carneegie Mellon University Funds.

Keywords:

" target="_blank"> Mathematics Subject Classification (2000): 05D40 68Q25

本文献已被 SpringerLink 等数据库收录！

设为首页 | 免责声明 | 关于勤云 | 加入收藏