Name
Title | ||
|---|---|---|
Threshold behaviors of a random constraint satisfaction problem with exact phase transitions |
Abstract | ||
|---|---|---|
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"c"r and p"c"r. 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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.ipl.2011.07.006 | Inf. Process. Lett. |
Keywords | Field | DocType |
rigorous study,threshold behavior,model rb,exact phase transition,control parameter,finite-size scaling analysis,critical value,np-complete problem,sharp satisfiability phase-transition phenomenon,finite problem size n,random constraint satisfaction problem,computational complexity,np complete problem,phase transition,constraint satisfaction problem,satisfiability | Discrete mathematics,Combinatorics,Phase transition,Satisfiability,Constraint satisfaction problem,Phenomenon,Scaling,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
111 | 20 | 0020-0190 |
Citations | PageRank | References |
3 | 0.38 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chunyan Zhao | 1 | 3 | 1.06 |
| Zhiming Zheng | 2 | 128 | 16.80 |