ITP OpenIR  > 理论物理所科研产出  > SCI论文
Zhou, Haijun; Zhou, HJ , Chinese Acad Sci, Inst Theoret Phys, Beijing 100080, Peoples R China
T -> 0 mean-field population dynamics approach for the random 3-satisfiability problem
Source PublicationPHYSICAL REVIEW E
KeywordK-satisfiability Problem Computational-complexity Cavity Method Phase Entropy States
AbstractDuring the past decade, phase-transition phenomena in the random 3-satisfiability (3-SAT) problem has been intensively studied by statistical physics methods. In this work, we study the random 3-SAT problem by the mean-field first-step replica-symmetry-broken cavity theory at the limit of temperature T -> 0. The reweighting parameter y of the cavity theory is allowed to approach infinity together with the inverse temperature beta with fixed ratio r=y/beta. Focusing on the system's space of satisfiable configurations, we carry out extensive population dynamics simulations using the technique of importance sampling, and we obtain the entropy density s(r) and complexity Sigma(r) of zero-energy clusters at different r values. We demonstrate that the population dynamics may reach different fixed points with different types of initial conditions. By knowing the trends of s(r) and Sigma(r) with r, we can judge whether a certain type of initial condition is appropriate at a given r value. This work complements and confirms the results of several other very recent theoretical studies.
2008
ISSN1539-3755
Volume77Issue:6Pages:-
Subject AreaPhysics
Indexed BySCI
Citation statistics
Cited Times:11[WOS]   [WOS Record]     [Related Records in WOS]
Document Type期刊论文
Identifierhttp://ir.itp.ac.cn/handle/311006/5524
Collection理论物理所科研产出_SCI论文
Corresponding AuthorZhou, HJ , Chinese Acad Sci, Inst Theoret Phys, Beijing 100080, Peoples R China
Recommended Citation
GB/T 7714
Zhou, Haijun,Zhou, HJ , Chinese Acad Sci, Inst Theoret Phys, Beijing 100080, Peoples R China. T -> 0 mean-field population dynamics approach for the random 3-satisfiability problem[J]. PHYSICAL REVIEW E,2008,77(6):-.
APA Zhou, Haijun,&Zhou, HJ , Chinese Acad Sci, Inst Theoret Phys, Beijing 100080, Peoples R China.(2008).T -> 0 mean-field population dynamics approach for the random 3-satisfiability problem.PHYSICAL REVIEW E,77(6),-.
MLA Zhou, Haijun,et al."T -> 0 mean-field population dynamics approach for the random 3-satisfiability problem".PHYSICAL REVIEW E 77.6(2008):-.
Files in This Item:
File Name/Size DocType Version Access License
T→0 mean-field popul(142KB) 开放获取LicenseApplication Full Text
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Zhou, Haijun]'s Articles
[Zhou, HJ , Chinese Acad Sci, Inst Theoret Phys, Beijing 100080, Peoples R China]'s Articles
Baidu academic
Similar articles in Baidu academic
[Zhou, Haijun]'s Articles
[Zhou, HJ , Chinese Acad Sci, Inst Theoret Phys, Beijing 100080, Peoples R China]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Zhou, Haijun]'s Articles
[Zhou, HJ , Chinese Acad Sci, Inst Theoret Phys, Beijing 100080, Peoples R China]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.