Tricritical points in random combinatorics: the (2+p)-SAT case

被引:28
作者
Monasson, R
Zecchina, R
机构
[1] Ecole Normale Super, Phys Theor Lab, CNRS, F-75231 Paris 05, France
[2] Univ Trieste, Int Ctr Theoret Phys, I-34100 Trieste, Italy
来源
JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL | 1998年 / 31卷 / 46期
关键词
D O I
10.1088/0305-4470/31/46/011
中图分类号
O4 [物理学];
学科分类号
0702 ;
摘要
The (2 + p)-satisfiability (SAT) problem interpolates between different classes of complexity theory and is thought to be of basic interest in understanding the onset of typical case complexity in random combinatorics. In this paper, a tricritical point in the phase diagram of the random (2 + p)-SAT problem is analytically computed using the replica approach and found to lie in the range 2/5 less than or equal to p(o) less than or equal to 0.416. These bounds on p(o) are in agreement with previous numerical simulations and rigorous results.
引用
收藏
页码:9209 / 9217
页数:9
相关论文
共 18 条
[1]  
ACHILIOPTAS D, 1997, P RALCOM 7, P1
[2]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[3]  
Chvatal V., 1992, Proceedings 33rd Annual Symposium on Foundations of Computer Science (Cat. No.92CH3188-0), P620, DOI 10.1109/SFCS.1992.267789
[4]   SPIN-GLASSES WITH P-SPIN INTERACTIONS [J].
GARDNER, E .
NUCLEAR PHYSICS B, 1985, 257 (06) :747-765
[5]  
GLIOZZI AS, STRUCTURE SPACE SOLU
[6]   A threshold for unsatisfiability [J].
Goerdt, A .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1996, 53 (03) :469-486
[7]  
Goerdt A., 1992, P 7 INT S MATH FDN C, P264
[8]  
Hayes B, 1997, AM SCI, V85, P108
[9]  
HOGG T, 1996, ARTIF INTELL, V81
[10]   CRITICAL-BEHAVIOR IN THE SATISFIABILITY OF RANDOM BOOLEAN EXPRESSIONS [J].
KIRKPATRICK, S ;
SELMAN, B .
SCIENCE, 1994, 264 (5163) :1297-1301