Article citationsMore>>

Achlioptas, D., Kirousis, L., Kranakis, E., Krizanc, D., Molloy, M. and Stamatiou, Y. (2001) Random Constraint Satisfaction: A More Accurate Picture. Constraints, 6, 329-344.
https://doi.org/10.1023/A:1011402324562

has been cited by the following article:

• TITLE: Sharp Thresholds for a Random Constraint Satisfaction Problem

  AUTHORS: Ya'nan Liu

  KEYWORDS: d-p-RB Model, Phase Transition, Domain Size, Constraint Tightness, Second Moment Method

  JOURNAL NAME: Open Journal of Applied Sciences, Vol.7 No.10, October 31, 2017

  ABSTRACT: The phenomenon of phase transition in constraint satisfaction problems (CSPs) plays a crucial role in the field of artificial intelligence and computational complexity theory. In this paper, we propose a new random CSP called d-p-RB model, which is a generalization of RB model on domain size d and constraint tightness p. In this model, the variable domain size dΕ [ nα, nny], and all constraints are uniformly divided into several groups with different constraint tightness p. It is proved by the second moment method that the d-p-RB model undergoes phase transition from a region where almost all instances are satisfiable to a region where almost all instances are unsatisfiable as the control parameter increases. Moreover, the threshold value at which the phase transition occurs is located exactly.