A Model Of Random Constraint Satisfaction Problems And Phase Transitions

Constraint satisfaction problem, or CSP in short, consists of variables and domains and constraints(constraint scopes and constraint relations), and asks whether or not there is an assignment to variables with values in domains such that the constraints are satisfied. Constraint satisfaction problems play very important roles in the many applied area, such as computer science, artificial intelligence. Random CSP models are the basis of the study of random CSPs. A good random CSP model, especially those models that can generate hard instances, is very important for us to study the nature of CSPs and evaluate different CSP algorithms.The earlier models with the constant domain size had a fatal flaw that they did not exhibit non-trivial satisfiability threshold. To overcome the deficiency of these models, some models restrict some special "structure" in the generated random instances with constant domain size. On the other hand some researchers began to focus on the case that the domain size grows with the number n of variables, such as the model RB.In chapter 2, motivated by k-SAT with growing k and the model RB we propose a new random CSP model, named the model d-k-CSP. For the new model d-k-CSP, if the domain size d and the length k of the constraint scopes satisfy that kln d≥(1+ε)ln n for an arbitrary positive realε, the model d-k-CSP exhibits sharp threshold, where In n= logen denotes the natural logarithm function with e being the natural base of the logarithm. If the domain size is constant, the length k of the constraint scopes will grow up to or over the logarithm of the number n of variables, which is the model k-CSP. If the domain size d= nα, the length k of the constraint scopes will be constant, which is the model RB.In chapter 3, we analyze the resolution complexity of the model d-k-CSP It is proved that almost all unsatisfiable instances of the model d-k-CSP have no tree-like resolution proofs of less than exponential size when the domain size d≥nαand the length k of constraints scopes is fixed. We give the experiments about the two cases of the domain size:d is constant and d= ln n. The experiments in the two cases illustrate that the model d-k-CSP will happen the satisfiability phase transition and the worse-cases happen around the phase transition point. On the other hand, the parameters d and k of the model d-k-CSP are growing up very slowly when the number of variables n is growing up. In summary, the model d-k-CSP can easily and naturally generate asymptotically non-trivial CSP instances, thus it is very suitable for testing the capability of CSP algorithms.To combine the advantages of linear CSP and the model d-k-CSP, we incorporate certain algebraic structure to the domains and constraint relations of the model d-k-CSP, hen introduce another type of random linear CSP model in chapter 4, named k-hyper-F-linear CSP. For each instance of the new proposed model, we assume that the domain could be any finite field F; the constraint relations are randomly chosen from the hyperplanes of the vector space Fk, where k is the length of constraint scopes. We exhibit theoretically the exact phase transition of the model k-hyper-F-linear CSP. When comparing with the linear CSP models we provide a more general formulation and a new proof based on a more general argument. Meantime random system of linear equations is the special case of the model k-hyper-F-linear CSP. In addtion we discuss the complexity of Gaussian elimination for testing satisfiability of the systems and find that the worst instances should be found at the phase transitions point.In the last chapter we give the conclusion of this paper.