正则3-SAT问题的相变现象  

Phase Transition Phenomenon of Regular 3-SAT Problem

作　　者：张明明[1] 许道云[1] 

机构地区：[1]贵州大学计算机科学与技术学院,贵阳550025

出　　处：《计算机科学》2016年第4期33-36,共4页Computer Science

基　　金：国家自然科学基金(61262006)资助

摘　　要：通过对3-CNF公式加以限制,要求其中每个变元出现的次数相同,引出正则3-SAT问题。进一步,通过对两种子句产生机制形成的(3,s)-CNF公式进行可满足性观察,发现在规模较小的情况下,正则3-CNF公式比非正则3-CNF公式更容易满足。从而推测与非正则3-SAT问题相比,正则3-SAT问题的相变点有偏移现象。最后,从变元自由度的角度对这一现象给出了定性解释。We considered the restriction on the 3-CNF formula on n Boolean variables{x1 ,x2, ……,xn }, in which each of the 2n literals occurs precisely times. We called such formulas as regular （3, s）-CNF formulas. Through the two kinds of clauses generating mechanism of （3, s）-CNF formula, we observed that the regular （3, s）- CNF formulas are easier to be satisfied than non-regular 3-CNF formulas while the input size is small. Thus we inferred that compared with non-regular 3-SAT, the transition point of regular 3-SAT problems has offset phenomenorL Finally we explained this phenomenon from a perspective of the number of the variable＇s degree of freedom.

关 键 词：正则CNF公式 SAT问题 相变 变元自由度 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]