2-3-SAT问题相变现象剖析及其应用
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

本文研究得到国家863高科技项目基金资助.


Analysis for Phase Transition of the 2-3-SAT Problem
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    3-SAT问题有一个非常奇妙的相变现象.对于固定的变量数N,合取范式的可满足概率随着子句个数K的变化而发生剧烈的变化;当K≈4.3*N 时,可满足概率急剧地从1变为0.相变现象决定了问题的难易分布,对于快速求解算法的设计有着非常重要的意义.文章着重讨论了SAT问题的更一般形式,即2-3-SAT问题的相变现象.研究了相变点处的2-子句和3-子句个数的关系,发现了2-子句和3-子句在约束能力意义下的当量关系,并提出了如何有效地利用2-3-SAT的相变现象.

    Abstract:

    There exists a very interesting feature in SAT(satisfiability) problem. With a fixed numbers of variables, the satifactory probability of an SAT instance change sharply from 1 to 0 while the number of clauses increasing, and the phase transition point is estimated to be K≈4.3*N. The phase transitions are of great importance to the efficient algorithms designing to solve the SAT problem. More generally, the phase transition of 2-3-SAT problem was discussed in this paper. The analysis of the location of the phase transition point of 2-3-SAT shows that there is an linear ratio between a 2-clause and a 3-clause in the sense of the constraint power which could help to design a more powerful heuristic for algorithms designing.

    参考文献
    相似文献
    引证文献
引用本文

白 硕,卜东波.2-3-SAT问题相变现象剖析及其应用.软件学报,1998,9(11):828-832

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:1997-03-11
  • 最后修改日期:1997-11-10
  • 录用日期:
  • 在线发布日期:
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号