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

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    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.

    Reference
    Related
    Cited by
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:May 27,1994
  • Revised:December 29,1994
  • Adopted:
  • Online:
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063