Author(s)

Xiaomei Shi^*

College of Science, University of Shanghai for Science and Technology, Shanghai, China.

This paper analyzes the resolution complexity of a random CSP model named model RB^mix, the instance of which is composed by constraints with different length. For model RB^mix, the existence of phase transitions has been established and the threshold points have been located exactly. By encoding the random instances into CNF formulas, it is proved that almost all instances of model RB^mix have no tree-like resolution proofs of less than exponential size. Thus the model RB^mix can generate abundant hard instances in the threshold. This result is of great significance for algorithm testing and complexity analysis in NP-complete problems.

Model RBmix, Tree-Like Resolution, Complexity, Hard Instances

Shi, X. (2017) Complexity Analysis of Mixed Constraint Satisfaction Problems. Open Journal of Applied Sciences, 7, 129-139. doi: 10.4236/ojapps.2017.74011.