| 摘要: |
| 3-SAT问题有一个非常奇妙的相变现象.对于固定的变量数N，合取范式的可满足概率随着子句个数K的变化而发生剧烈的变化;当K≈4.3*N 时,可满足概率急剧地从1变为0.相变现象决定了问题的难易分布,对于快速求解算法的设计有着非常重要的意义.文章着重讨论了SAT问题的更一般形式，即2-3-SAT问题的相变现象.研究了相变点处的2-子句和3-子句个数的关系，发现了2-子句和3-子句在约束能力意义下的当量关系，并提出了如何有效地利用2-3-SAT的相变现象. |
| 关键词: NP完全问题,合取范式,SAT问题,相变现象,可满足概率,2-3-当量. |
| DOI： |
| 分类号: |
| 基金项目:本文研究得到国家863高科技项目基金资助. |
|
| Analysis for Phase Transition of the 2-3-SAT Problem |
|
BAI Shuo,BU Dong-bo
|
| 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. |
| Key words: SAT problem, 2-3-SAT, phase transition, 2-3-ratio, constraint power. |
