Abstract: We considered the restriction on the 3-CNF formula on n Boolean variables｛x₁,x₂,…,x_n｝,in which each of the 2n literals occurs precisely ｛x₁,x₁,…,x_n,x_n｝ 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 phenomenon.Finally we explained this phenomenon from a perspective of the number of the variable’s degree of freedom.

Key words: Regular CNF formula,SAT problem,Phase transition,Variable’s degrees of freedom