Approximating the unsatisfiability threshold of random formulas-猫眼课题宝

DOI：

10.1002/(sici)1098-2418(199805)12:3

发表时间：

1998-05

期刊：

Random Struct. Algorithms

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

L. Kirousis;E. Kranakis;D. Krizanc;Y. Stamatiou

设f是一个随机布尔公式，它是3-SAT的一个实例。我们考虑计算最小真实的数k的问题，使得如果子句数与f的变量数之比严格超过k，则f几乎肯定是不可满足的。通过一个众所周知的和或多或少直截了当的论点，可以证明kF5.191。Kamath等人通过首先为占用问题提供新的改进边界，将该上限改进为4.758。有强有力的实验证据表明，k值约为4.2。在这项工作中，我们定义，在随机公式f，一个随机变量的递减序列，使得，如果其中任何一个的期望值收敛到零，那么f几乎肯定是不可满足的。通过让序列的第一项的期望值收敛到零，我们得到，通过简单和初等的计算，k等于4.667的上界。从序列第二项的期望值，我们得到值4.601q。这项工作是在第一作者访问卡尔顿大学计算机科学学院时进行的，并得到了NSERC自然科学和工程研究理事会的部分支持。此外，还获得了帕特雷大学的公休假补助金。第二和第三位作者的赠款来自NSERC自然科学和工程研究。加拿大理事会。在本研究的最后阶段，第一和最后一位作者也被部分删除。由欧盟ESPRIT长期研究项目ALCOM-IT项目编号20244支持。[2]本文的扩展摘要发表在第四届欧洲算法研讨会论文集上，ESA'96，1996年9月25日]27日，西班牙巴塞罗那，Springer-Verlag，LNCS，。pp. [27]38 .该扩展摘要由本论文的前三位作者合著。联系人：L。M. John Wiley & Sons，Inc. CCC 1042-9832r98r030253-17 253

Let f be a random Boolean formula that is an instance of 3-SAT. We consider the problem of computing the least real number k such that if the ratio of the number of clauses over the number of variables of f strictly exceeds k , then f is almost certainly unsatisfiable. By a well-known and more or less straightforward argument, it can be shown that kF5.191. This upper bound was improved by Kamath et al. to 4.758 by first providing new improved bounds for the occupancy problem. There is strong experimental evidence that the value of k is around 4.2. In this work, we define, in terms of the random formula f, a decreasing sequence of random variables such that, if the expected value of any one of them converges to zero, then f is almost certainly unsatisfiable. By letting the expected value of the first term of the sequence converge to zero, we obtain, by simple and elementary computations, an upper bound for k equal to 4.667. From the expected value of the second term of the sequence, we get the value 4.601q . In general, by letting the U This work was performed while the first author was visiting the School of Computer Science, Carleton Ž University, and was partially supported by NSERC Natural Sciences and Engineering Research Council . of Canada , and by a grant from the University of Patras for sabbatical leaves. The second and third Ž authors were supported in part by grants from NSERC Natural Sciences and Engineering Research . Council of Canada . During the last stages of this research, the first and last authors were also partially Ž . supported by EU ESPRIT Long-Term Research Project ALCOM-IT Project No. 20244 . †An extended abstract of this paper was published in the Proceedings of the Fourth Annual European Ž Symposium on Algorithms, ESA’96, September 25]27, 1996, Barcelona, Spain Springer-Verlag, LNCS, . pp. 27]38 . That extended abstract was coauthored by the first three authors of the present paper. Correspondence to: L. M. Kirousis Q 1998 John Wiley & Sons, Inc. CCC 1042-9832r98r030253-17 253

Approximating the unsatisfiability threshold of random formulas

文献摘要

被引文献

相似文献