Threshold behaviors of a random constraint satisfaction problem with exact phase transitions

Chunyan Zhao; Zhiming Zheng

doi:10.1016/j.ipl.2011.07.006

Threshold behaviors of a random constraint satisfaction problem with exact phase transitions

Chunyan Zhao^*
, Zhiming Zheng

^*此作品的通讯作者

Beihang University
Ministry of Education of the People's Republic of China

科研成果: 期刊稿件 › 文章 › 同行评审

8 引用（Scopus）

摘要

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 ^rcr and ^pcr. 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.

源语言	英语
页（从-至）	985-988
页数	4
期刊	Information Processing Letters
卷	111
期	20
DOI	https://doi.org/10.1016/j.ipl.2011.07.006
出版状态	已出版 - 31 10月 2011
已对外发布	是

访问文件

10.1016/j.ipl.2011.07.006

其它文件与链接

链接到 Scopus 的出版物

引用此

@article{af0eb4b82a3341f9a794b27a40479351,

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 rcr and pcr. 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.",

keywords = "Computational complexity, Constraint satisfaction problem, Finite-size scaling, Model RB, Phase transition, Threshold behavior",

author = "Chunyan Zhao and Zhiming Zheng",

year = "2011",

month = oct,

day = "31",

doi = "10.1016/j.ipl.2011.07.006",

language = "英语",

volume = "111",

pages = "985--988",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "20",

}

TY - JOUR

T1 - Threshold behaviors of a random constraint satisfaction problem with exact phase transitions

AU - Zhao, Chunyan

AU - Zheng, Zhiming

PY - 2011/10/31

Y1 - 2011/10/31

N2 - 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 rcr and pcr. 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.

AB - 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 rcr and pcr. 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.

KW - Computational complexity

KW - Constraint satisfaction problem

KW - Finite-size scaling

KW - Model RB

KW - Phase transition

KW - Threshold behavior

UR - https://www.scopus.com/pages/publications/79960850986

U2 - 10.1016/j.ipl.2011.07.006

DO - 10.1016/j.ipl.2011.07.006

M3 - 文章

AN - SCOPUS:79960850986

SN - 0020-0190

VL - 111

SP - 985

EP - 988

JO - Information Processing Letters

JF - Information Processing Letters

IS - 20

ER -

Threshold behaviors of a random constraint satisfaction problem with exact phase transitions

摘要

访问文件

其它文件与链接

指纹

引用此