Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Random k-SAT: the limiting probability for satisfiability for moderately growing k. | Random k-SAT the limiting probability for satisfiability for moderately growing k Amin Coja-Oghlan Alan Frieze Department of Mathematical Sciences Carnegie Mellon University PittsbUrgh PA 15213 USA. acoghlan@inf.ed.ac.uk alan@random.math.cmu.edu Submitted Sep 11 2007 Accepted Jan 17 2008 Published Feb 4 2008 Mathematics Subject Classihcation 05C88 Abstract We consider a random instance Im Im n k of k-SAT with n variables and m clauses where k k n satishes k log2 n 1. Let m 2k n In 2 c for an absolute constant c. We prove that TW. T -e c lim Pr Im is satishable e nn 1 Introduction An instance of k-SAT is defined by a set of variables V f X1 x2 . xng and a set of clauses C1 C2 . Cm. We will let clause Ci be a sequence Ai 1 Ai 2 . Ai k where each literal Ai i is a member of L V u V where V fx1 x2 . xng. In our random model each Ai l is chosen independently and uniformly from L. 1 We denote the resulting random instance by Im Im n k. Supported by DFG COJ 646. Supported in part by NSF grant CCF-0502793 1 We are aware that this allows clauses to have repeated literals or instances of x x. The focus of the paper is on k O ln n although the main result is valid for larger k. Thus most clauses will not have repeated clauses or contain a pair x x. THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 N2 1 Random k-SAT has been well studied to say the least see the references in 6 . If k 2 then it is known that there is a satisfiability threshold at around m n. More precisely if e 0 is fixed and I is a random instance of 2-SAT then lim Pr Im n 2 is satisfiable nn Í0 m 1 e n m 1 e n Thus random 2-SAT is now pretty much understood. For k 3 the story is very different. It is now known that a threshold for satisfiability exists in some not completely satisfactory sense Friedgut 5 . There has been considerable work on trying to find estimates for this threshold in the case k 3 see the references in 6 . Currently the best lower bound for the threshold is 3.52 due to Hajiaghayi and Sorkin
