• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Foundations of Computer Science, 1992. Proceedings., 33rd Annual Symposium on >Mick gets some (the odds are on his side) (satisfiability)
【24h】

Mick gets some (the odds are on his side) (satisfiability)

机译：米克得到一些（赔率就在他身边）（满足）

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Consider a randomly generated boolean formula F (in the conjunctive normal form) with m clauses of size k over n variables; k is fixed at any value greater than 1, but n tends to infinity and m = (1 + o(1))cn for some c depending only on k. It is easy to see that F is unsatisfiable with probability 1-o(1) whenever c<(ln 2)2/sup k/; the authors complement this observation by proving that F is satisfiable with probability 1-o(1) whenever c>(0.25)2/sup k//k; in fact, they present a linear-time algorithm that satisfies F with probability 1-o(1). In addition, they establish a threshold for 2-SAT: if k = 2 then F is satisfiable with probability 1-o(1) whenever c>1 and unsatisfiable with probability 1-o(1) whenever c<1.
机译：考虑一个随机生成的布尔公式F（合取范式），在n个变量上具有m个大小为k的子句; k固定为任何大于1的值，但对于某些c，n趋于无穷大，并且m =（1 + o（1））cn仅取决于k。容易看出，每当c <（ln 2）2 / sup k /;时，F的概率为1-o（1）是不满足的。作者证明，只要c>（0.25）2 / sup k // k，F的概率就可以满足1-o（1）。实际上，他们提出了一种线性时间算法，该算法以1o（1）的概率满足F。此外，它们为2-SAT建立阈值：如果k = 2，则无论何时c> 1，F的概率为1-o（1），而当c <1的F的概率为1-o（1）。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号