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

  • Article
  • | |
  • Metrics
  • |
  • Reference [1]
  • |
  • Related
  • |
  • Cited by
  • | |
  • Comments
    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.

    Reference
    1  Bai Shuo, Bu Dong-bo. Modeling phase transition 3-SAT problem. In: Proceedings of the 2nd International Competition and Symposium on SAT Problem. Beijing, 1996 2  Garey M R, Johnson D S. Computers and intractability: a guide to the theory of NP-completeness. San Francisco: Freeman W H and Company, 1979 3  Mitchell D, Selman B, Levesque H. Hard and easy distributions of SAT problem. In: Proceedings of the 10th Conference on Artificial Intelligence(AAAI'92). San Jose, CA, July 1992. 459~465 4  Dubois O, Carlier J. Probalbilitistic approach to the satisfiability problem. Theoretical Computer Science, 1991,81 5  Selman B. Stochastic search and phase transitions: AI meets physics. In: Proceedings of the International Joint Conference on Artificial Intelligence'95, Extended Abstract. 1995 6  Gent I P, Walsh T. Easy problems are sometimes hard. In: Proceedings of the DIMACS Challenge'93. 1993 7  Dubois O, Andre P, Boufkhad Y et al. SAT versus UNSAT. In: Proceedings of the DIMACS Challenge'93. 1993
    Related
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:4808
  • PDF: 4857
  • HTML: 0
  • Cited by: 0
History
  • Received:March 11,1997
  • Revised:November 10,1997
You are the first2038782Visitors
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