A Class Of Random Constraint Satisfaction Problems, Phase Transitions And Related Computing Complexity Research

In this paper,we first review the history of the NP-Complete problem and some related researches,and then we propose two new random constraint satisfaction problem(CSP) models(i.e.model RB'/RD'),which are revision to model RB/RD.Moreover,from a theoretical perspective,we will show the existence of phase transitions,and ever establish the exact location of the threshold points.Finally, we analyze the resolution complexity of model RB'/RD'.By encoding CSPs into CNF formulas,it is proved that almost all instances of model RB'/RD' has no tree-like resolutions proofs of less than 2~Ω(n),i.e.model RB'/RD' can produce many hard instances.