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

摘要

通过对3-CNF公式加以限制,要求其中每个变元出现的次数相同,引出正则3-SAT问题.进一步,通过对两种子句产生机制形成的(3,s)-CNF公式进行可满足性观察,发现在规模较小的情况下,正则3-CNF公式比非正则3-CNF公式更容易满足.从而推测与非正则3-SAT问题相比,正则3-SAT问题的相变点有偏移现象.最后,从变元自由度的角度对这一现象给出了定性解释.