二元可满足性问题有解的充要条件
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:


AN SUFFICIENT AND NECESSARY CONDITION FOR 2SAT PROBLEM
Author:
Affiliation:

Fund Project:

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

    二元可满足性问题是一个多项式可解的问题.本文首先证明了该问题有解的充要条件,然后给出了判定该问题的一个新的多项式算法.如果判定某个表达式是可满足的话,那么求解算法不需要任何回溯就能准确地给出它的每个解.本文试图通过对二元可满足性的研究为研究其它问题提供一点启示.

    Abstract:

    Satisfiability (2SAT) is a determinable problem in polynomial time. This paper proves a sufficient and necessary condition for 2SAT problem, and presents a new polynomial algorithm for 2SAT problem. In addition, if one 2 CNF expression is satisfiable, the algorithm for solution can give every solution without backtracking. This paper tries to give some idea for other problem through the study of 2SAT problem.

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

吴向军,余丰人.二元可满足性问题有解的充要条件.软件学报,1996,7(1):51-58

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

京公网安备 11040202500063号