变元正负出现概率受控的随机正则k-SAT问题研究

The regular random (k,r)-SAT problem is a special k-SAT problem obtained by restricting the k-CNF instances where each variable occurs precisely r times and both the probabilities of the variable’s positive and negative occurrences are 1/2. It is worth to study theoretically because it is much more difficult to solve than the general random k-SAT problem. In this project, we will study a new random equilibrium k-SAT problem, named regular random p-(k,r)-SAT problem, which is achieved by restricting the k-SAT problem instances where each variable occurs precisely r times and each of the positive variable occurs probability is p, correspondingly, the negative one is 1-p. Therefore, it is more general than the regular random (k,r)-SAT problem... This project will investigate the instances generation model, the easy and the hard subclass distributions, the structure characteristics of hard instances, the phase transition phenomenons and decision algorithms to the regular random (k,r)- SAT problem. It is expected that the research results will help us to further explore the properties of the random equilibrium k-SAT problems and recognize the essential of the NP complete problems. Futhermore, These research results would also help us to detect the general mathematical phenomena and design some more effective decision algorithms for the SAT problem.

随机正则(k,r)-SAT问题是限制每个变元恰好出现r次且其变元正、负出现概率均为1/2的随机k-SAT子问题，因其相变点处的随机正则(k,r)-CNF实例远比同规模相应相变点处的随机k-CNF实例更难判定而极具研究价值。本项目拟研究一种变元正、负出现概率受控且比随机正则(k,r)-SAT问题更为泛化的随机均衡k-SAT问题，即研究每个变元恰好出现r次且其以p的概率正出现、而以1-p的概率负出现的随机正则p-(k,r)-SAT问题。我们将围绕该问题的实例生成模型、易解子类分布情况、解空间的结构特征、可满足相变现象、难解实例特征、难解实例构造、判定算法等方面对其进行深入的研究，以期进一步探索随机均衡k-SAT问题的相关性质，为进一步认识NP完全问题的本质特性、发现SAT问题的一般数学现象和设计更为有效的SAT判定算法奠定基础。

随机正则(k,r)-SAT问题是限制每个变元恰好出现r次且其变元正、负出现概率均为1/2的随机k-SAT子问题，因其相变点处的随机正则(k,r)-CNF实例远比同规模相应相变点处的随机k-CNF实例更难判定而极具研究价值。本项目研究了变元正、负出现概率受控且比随机正则(k,r)-SAT问题更为泛化的随机均衡k-SAT问题，即研究每个变元恰好出现r次且其以p的概率正出现、而以1-p的概率负出现的随机正则p-(k,r)-SAT问题。我们围绕该问题的实例生成模型、易解子类分布情况、解空间的结构特征、可满足相变现象、难解实例特征、难解实例构造、判定算法等方面对其进行了深入的研究，以期进一步为探索随机均衡k-SAT问题的相关性质，为进一步认识NP完全问题的本质特性、发现SAT问题的一般数学现象和设计更为有效的SAT判定算法奠定基础。