Threshold behaviors of a random constraint satisfaction problem with exact phase transitions
We consider a random constraint satisfaction problem named model RB, which exhibits a sharp satisfiability phase-transition phenomenon when the control parameters pass through the critical values denoted by r(cr) and p(cr). Using finite-size scaling analysis, we bound the width of the transition region for finite problem size n, which might be the first rigorous study on the threshold behaviors of NP-complete problems. (C) 2011 Elsevier B.V. All rights reserved.
threshold behavior constraint satisfaction problem phase transition model rb finite-size scaling computational complexity