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 rcrrcr and pcrpcr. 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.

► We study a random constraint satisfaction problem with exact phase transitions. ► Bound the width of the transition region for finite problem size. ► The first rigorous study on the threshold behaviors of NP-complete problems.