Review of phase transition in satisfiability problems

doi:10.11772/j.issn.1001-9081.2023111559

Journal of Computer Applications ›› 2024, Vol. 44 ›› Issue (11): 3503-3512.DOI: 10.11772/j.issn.1001-9081.2023111559

• Advanced computing • Previous Articles Next Articles

Review of phase transition in satisfiability problems

Qingyuan PENG¹, Xiaofeng WANG¹^,²(), Junxia WANG¹, Yingying HUA¹, Ao TANG¹, Fei HE¹

^1.School of Computer Science and Engineering，North Minzu University，Yinchuan Ningxia 750021，China
^2.Key Laboratory of Image and Graphics Intelligent Processing of State Ethnic Affairs Commission （North Minzu University），Yinchuan Ningxia 750021，China

Received:2023-11-13 Revised:2023-12-28 Accepted:2024-01-19 Online:2024-02-29 Published:2024-11-10
Contact: Xiaofeng WANG
About author:PENG Qingyuan， born in 1998， M. S. candidate. Her research interests include algorithm analysis and design.
WANG Junxia， born in 2000， M. S. candidate. Her research interests include algorithm analysis and design.
HUA Yingying， born in 2000， M. S. candidate. Her research interests include algorithm analysis and design.
TANG Ao， born in 2002， M. S. candidate. His research interests include algorithm analysis and design.
HE Fei， born in 1999， M. S. candidate. His research interests include algorithm analysis and design.
Supported by:
National Natural Science Foundation of China(62062001);Ningxia Youth Top Talent Project(2021)

可满足性问题相变研究综述

彭庆媛¹, 王晓峰¹^,²(), 王军霞¹, 华盈盈¹, 唐傲¹, 何飞¹

^1.北方民族大学计算机科学与工程学院，银川 750021
^2.图形图像智能处理国家民委重点实验室（北方民族大学），银川 750021

通讯作者: 王晓峰
作者简介:彭庆媛（1998—），女，云南丽江人，硕士研究生，CCF会员，主要研究方向：算法分析与设计
王军霞（2000—），女，甘肃白银人，硕士研究生，CCF会员，主要研究方向：算法分析与设计
华盈盈（2000—），女，河南南阳人，硕士研究生，CCF会员，主要研究方向：算法分析与设计
唐傲（2002—），男，湖南邵阳人，硕士研究生，CCF会员，主要研究方向：算法分析与设计
何飞（1999—），男，湖南永州人，硕士研究生，CCF会员，主要研究方向：算法分析与设计。
基金资助:
国家自然科学基金资助项目(62062001);宁夏青年拔尖人才项目(2021)

Abstract

Abstract:

Constraint Satisfaction Problem （CSP） is a combinatorial optimization problem in the field of theoretical computer science. As a special case of CSP， the SATisfiability （SAT） problem is a hot issue in the fields such as theoretical computer science， mathematical logic and artificial intelligence. Phase transition is a phenomenon in satisfiability problems. The study of the phase transition phenomenon and phase transition mechanism of satisfiability problems have important guiding significance to deeply understand the essence of being hard to solve and general mathematical phenomena of satisfiability problems as well as design more efficient algorithms to solve satisfiability problems. Therefore， according to some important research results of scholars at home and abroad in recent years on phase transition phenomenon in satisfiability problems， firstly， the related knowledge of phase transition in satisfiability problems as well as the probability analysis methods and instance generation models of satisfiability problem were introduced. Then， the phase transition point solution methods and phase transition thresholds of unsatisfiable phase transition and satisfiable phase transition in satisfiability problems were summarized and analyzed. Finally， the research trends of phase transition in satisfiability problems were prospected.

Key words: SATisfiability (SAT) Problem, probability analysis method, instance generation model, unsatisfiable phase transition, satisfiable phase transition

摘要：

约束满足问题（CSP）是理论计算机科学领域的组合优化问题，可满足性问题（SAT问题）作为CSP中的一种特殊情形，是理论计算机科学、数理逻辑和人工智能等领域十分关注的热点问题。相变是SAT问题中存在的一种现象，而研究SAT问题的相变现象和相变机制对深入认识SAT问题的难解本质和一般数学现象以及设计更高效的算法求解SAT问题有重要的指导意义。因此，根据近年来国内外学者针对SAT问题的相变现象取得的一些重要研究成果，首先介绍了SAT问题相变的相关知识以及SAT问题的概率分析方法和实例生成模型，其次总结并分析了SAT问题的不可满足相变和可满足相变这两种相变的相变点求解方法和相变阈值，最后展望了SAT问题相变的研究趋势。

关键词: 可满足性问题, 概率分析方法, 实例生成模型, 不可满足相变, 可满足相变

CLC Number:

TP301.6

Qingyuan PENG, Xiaofeng WANG, Junxia WANG, Yingying HUA, Ao TANG, Fei HE. Review of phase transition in satisfiability problems[J]. Journal of Computer Applications, 2024, 44(11): 3503-3512.

彭庆媛, 王晓峰, 王军霞, 华盈盈, 唐傲, 何飞. 可满足性问题相变研究综述[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3503-3512.

Figures/Tables 10

Fig. 1 Technical organization chart for this paper

Fig. 2 Factor graph representation of CNF formula F

Fig. 3 Curves of satisfiable probability and solving difficulty of SAT problem

Fig. 4 Schematic diagram of solution space of satisfiability problem varying with constraint density

Fig. 5 Schematic diagrams of cluster varying with constraint density

Tab. 1 Clustering phase transition point and condensation phase transition point of random k-SAT problem

$k$ -SAT	$α d$	$α c$
$k = 2$	1.000	1.000
$k = 3$	3.859	3.859
$k = 4$	9.380	9.547
$k = 5$	19.160	20.800
$k = 6$	36.530	43.080

Tab. 1 Clustering phase transition point and condensation phase transition point of random k-SAT problem

$k$ -SAT	$α d$	$α c$
$k = 2$	1.000	1.000
$k = 3$	3.859	3.859
$k = 4$	9.380	9.547
$k = 5$	19.160	20.800
$k = 6$	36.530	43.080

Tab. 2 Satisfiability phase transition threshold of random 3-SAT problem

相变上下界	文献序号	发表年	阈值
上界	［50］	2000	4.506
	［51］	2006	4.571
	［49］	2009	4.489 8
下界	［52］	2000	3.26
	［53］	2003	3.42
	［51］	2006	3.52

Fig. 6 Complexity of experimentally solving uniform 3-SAT and Reg 3-SAT problems

Fig. 7 Phase transition in Reg 3-SAT problems

Tab. 3 Bounds on satisfiable phase transition thresholds for strictly regular random （k，r）-SAT problems

$k$	$r$	下界	上界
3	4	2.667	3.782 22
4	16	8	9.107 76
7	296	84.571	85.879 1
10	3 524	704.8	705.953 3
15	170 298	22 706.4	22 707.5
17	772 182	90 844.94	90 845.9

Tab. 3 Bounds on satisfiable phase transition thresholds for strictly regular random （k，r）-SAT problems

$k$	$r$	下界	上界
3	4	2.667	3.782 22
4	16	8	9.107 76
7	296	84.571	85.879 1
10	3 524	704.8	705.953 3
15	170 298	22 706.4	22 707.5
17	772 182	90 844.94	90 845.9

References 72

1	MACKWORTH A K. Consistency in networks of relations［J］. Artificial Intelligence， 1977， 8（1）： 99-118.
2	JOHNSON D S. The NP-completeness column： an ongoing guide［J］. Journal of Algorithms， 1987， 6（3）：438-448.
3	DECHTER R， PEARL J. Network-based heuristics for constraint-satisfaction problems［J］. Artificial Intelligence， 1987， 34（1）： 1-38.
4	CHEESEMAN P C， KANEFSKY B， TAYLOR W M. Where the really hard problems are［C］// Proceedings of the 12th International Joint Conference on Artificial Intelligence： Volume 1. San Francisco： Morgan Kaufmann Publishers Inc.， 1991： 331-337.
5	刘燕丽，徐振兴，熊丹.基于动态奖惩的分支策略的SAT完备算法［J］.计算机应用， 2017，37（12）：3487-3492.
	LIU Y L， XU Z X， XIONG D. Exact SAT algorithm based on dynamic branching strategy of award and punishment［J］. Journal of Computer Applications， 2017， 37（12）： 3487-3492.
6	赵星宇，王晓峰，杨易，等.求解恰当可满足性问题的随机局部搜索算法［J］.计算机应用，2024，44（3）：842-848.
	ZHAO X Y， WANG X F， YANG Y， et al. Stochastic local search algorithm for solving exact satisfiability problem［J］. Journal of Computer Applications， 2024， 44（3）： 842-848.
7	庞立超，王晓峰，谢志新，等.随机正则3-可满足性问题的解簇结构分析［J］.计算机应用，2024，44（7）：2137-2143.
	PANG L C， WANG X F， XIE Z X， et al. Solution cluster structure analysis of random regular 3-satisfiability problems［J］. Journal of Computer Applications， 2024， 44（7）： 2137-2143.
8	ALYAHYA T N， BACHIR MENAI M EL， MATHKOUR H. On the structure of the Boolean satisfiability problem： a survey［J］. ACM Computing Surveys， 2022， 55（3）： No.46.
9	牛鹏飞，王晓峰，芦磊，等.随机约束满足问题相变研究综述［J］.计算机工程与科学，2022，44（7）：1321-1330.
	NIU P F， WANG X F， LU L， et al. Review of phase transition of random constraint satisfaction problems［J］. Computer Engineering and Science， 2022， 44（7）： 1321-1330.
10	谷文祥，黄平，朱磊，等.人工智能问题中的相变现象研究［J］.计算机科学，2011，38（5）：1-7.
	GU W X， HUANG P， ZHU L， et al. Research of phase transition in artificial intelligence［J］. Computer Science， 2011， 38（5）：1-7.
11	BANERJI R B. Formal Techniques in Artificial Intelligence： a Sourcebook［M］. New York： Elsevier Science Inc.， 1990：35-62.
12	ACHLIOPTAS D， PERES Y. The threshold for random k-SAT is 2 ^k log 2-O（k）［J］. Journal of the American Mathematical Society， 2004， 17（4）： 947-973.
13	VIZEL Y， WEISSENBACHER G， MALIK S. Boolean satisfiability solvers and their applications in model checking［J］. Proceedings of the IEEE， 2015， 103（11）： 2021-2035.
14	KSCHISCHANG F R， FREY B J， LOELIGER H A. Factor graphs and the sum-product algorithm［J］. IEEE Transactions on Information Theory， 2001， 47（2）： 498-519.
15	ERDÖS P， RÉNYI A. On the evolution of random graphs［J］. A Matematikai Kutató Intézet Közleményei， 1960， 5（1/2）： 17-60.
16	MONASSON R， ZECCHINA R， KIRKPATRICK S， et al. Determining computational complexity from characteristic ‘phase transitions’［J］. Nature， 1999， 400（6740）： 133-137.
17	MITZENMACHER M， UPFAL E.概率与计算：算法与数据分析中的随机化和概率技术（原书第2版）［M］.冉启康，译.北京：机械工业出版社，2020：36.
	MITZENMACHER M， UPFAL E. Probability and computing： randomized algorithms and probabilistic analysis （the 2nd edition of the original book）［M］. RAN Q K， translated. Beijing： China Machine Press， 2020： 36.
18	HARDY G H， LITTLEWOOD J E， POLYA G. Inequalities， Cambridge Mathematical Library［M］. 2nd ed. Cambridge： Cambridge University Press， 1988： 43-44.
19	ACHLIOPTAS D， MOORE C. Random k-SAT： two moments suffice to cross a sharp threshold［J］. SIAM Journal on Computing， 2006， 36（3）： 740-762.
20	WORMALD N C. Models of random regular graphs［M］// LAMB J D， PREECE D A. Surveys in Combinatorics， London Mathematical Society Lecture Note Series. Cambridge： Cambridge University Press， 1999： 239-298.
21	GOLDBERG A. Average case complexity of the satisfiability problem［C］// Proceedings of the 4th Workshop on Automated Deduction. Berlin： Springer， 1979： 1-16.
22	KAUTZ H， RUAN Y， ACHLIOPTAS D， et al. Balance and filtering in structured satisfiable problems［C］// Proceedings of the 17th International Joint Conference on Artificial Intelligence： Volume 1. San Francisco： Morgan Kaufmann Publishers Inc.， 2001： 351-356.
23	FRANCO J， PAULL M. Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem［J］. Discrete Applied Mathematics， 1983， 5（1）： 77-87.
24	ACHLIOPTAS D， GOMES C P， KAUTZ H A， et al. Generating satisfiable problems instances［C］// Proceedings of the 17th National Conference on Artificial Intelligence / 12th Conference on Innovative Applications of Artificial Intelligence. Menlo Park， CA： AAAI Press， 2000： 256-261.
25	BOUFKHAD Y， DUBOIS O， INTERIAN Y， et al. Regular random k-SAT： properties of balanced formulas［J］. Journal of Automated Reasoning， 2005， 35： 181-200.
26	RATHI V， AURELL E， RASMUSSEN L， et al. Bounds on threshold of regular random k-SAT［C］// Proceedings of the 2010 International Conference on Theory and Applications of Satisfiability Testing， LNCS 6175. Berlin： Springer， 2010： 264-277.
27	JANSON S， ŁUCZAK T， RUCINSKI A. Random Graphs［M］. New York： John Wiley & Sons， Inc.， 2000： 235-236.
28	周锦程，许道云，卢友军，等.严格随机正则（3， s）-SAT模型及其相变现象［J］.北京航空航天大学学报，2016，42（12）：2563-2571.
	ZHOU J C， XU D Y， LU Y J， et al. Strictly regular random （3， s）-SAT model and its phase transition phenomenon［J］. Journal of Beijing University of Aeronautics and Astronautics， 2016， 42（12）： 2563-2571.
29	周锦程，许道云，卢友军.随机正则（k，r）-SAT问题的可满足临界［J］.软件学报，2016，27（12）：2985-2993.
	ZHOU J C， XU D Y， LU Y J. Satisfiability threshold of the regular random （k，r）‑SAT problem［J］. Journal of Software， 2016， 27（12）： 2985-2993.
30	LI W， DING Y， YANG Y， et al. Parameterized algorithms of fundamental NP-hard problems： a survey［J］. Human-Centric Computing and Information Sciences， 2020， 10： No.29.
31	AURELL E， GORDON U， KIRKKPATRICK S. Comparing beliefs， surveys， and random walks［C］// Proceedings of the 17th International Conference on Neural Information Processing Systems. Cambridge： MIT Press， 2004： 49-56.
32	McALLESTER D， SELMAN B， KAUTZ H. Evidence for invariants in local search［C］// Proceedings of the14th National Conference on Artificial Intelligence / 9th Conference on Innovative Applications of Intelligence. Menlo Park， CA： AAAI Press， 1997： 321-326.
33	KRZ̧AKAŁA F， MONTANARI A， RICCI-TERSENGHI F， et al. Gibbs states and the set of solutions of random constraint satisfaction problems［J］. Proceedings of the National Academy of Sciences of the United States of America， 2007， 104（25）： 10318-10323.
34	MÉZARD M， RICCI-TERSENGHI F， ZECCHINA R. Two solutions to diluted p-spin models and XORSAT problems［J］. Journal of Statistical Physics， 2003， 111（3）： 505-533.
35	MÉZARD M， MORA T， ZECCHINA R. Clustering of solutions in the random satisfiability problem［J］. Physical Review Letters， 2005， 94（19）： No.197205.
36	MANEVA E， SINCLAIR A. On the satisfiability threshold and clustering of solutions of random 3-SAT formulas［J］. Theoretical Computer Science， 2008， 407（1/2/3）： 359-369.
37	ACHLIOPTAS D， COJA-OGHLAN A， RICCI-TERSENGHI F. On the solution-space geometry of random constraint satisfaction problems［J］. Random Structures and Algorithms， 2011， 38（3）： 251-268.
38	莫孝玲，许道云.CNF公式赋值空间上可满足解的概率性质［J］.计算机科学与探索，2018，12（11）：1852-1861.
	MO X L， XU D Y. Probabilistic properties of satisfiable solutions on space of assignments for CNF formula［J］. Journal of Frontiers of Computer Science and Technology， 2018， 12（11）： 1852-1861.
39	KRISHNAMURTHY S. Exact satisfiability threshold for k‑satisfiability problems on a Bethe lattice［J］. Physical Review. E， Statistical， Nonlinear， and Soft Matter Physics， 2015， 92（4）： No.042144.
40	MONTANARI A， RICCI-TERSENGHI F， SEMERJIAN G. Clusters of solutions and replica symmetry breaking in random k‑satisfiability［J］. Journal of Statistical Mechanics： Theory and Experiment， 2008， 2008（4）： No.P04004.
41	ACHLIOPTAS D， RICCI-TERSENGHI F. Random formulas have frozen variables［J］. SIAM Journal on Computing， 2009， 39（1）： 260-280.
42	BAPST V， COJA-OCHLAN A. The condensation phase transition in the regular k-SAT model［EB/OL］. ［2023-11-10］..
43	MITCHELL D， SELMAN B， LEVESQUE H. Hard and easy distributions of SAT problems［C］// Proceedings of the 10th National Conference on Artificial Intelligence. Menlo Park， CA： AAAl Press， 1992： 459-465.
44	MAHAJAN Y S， FU Z， MALIK S. Zchaff2004： an efficient SAT solver［C］// Proceedings of the 2004 International Conference on Theory and Applications of Satisfiability Testing， LNCS 3542. Berlin： Springer， 2005： 360-375.
45	KROC L， SABHARWAL A， SELMAN B. Survey propagation revisited［C］// Proceedings of the 23rd Conference on Uncertainty in Artificial Intelligence. Arlington， VA： AUAI Press， 2007： 217-226.
46	DUBOIS O， MONASSON R， SELMAN B， et al. Lower bounds for random 3-SAT via differential equations［J］. Theoretical Computer Science， 2001， 265（1/2）： 159-185.
47	MÉZARD M， ZECCHINA R. Random K-satisfiability problem： from an analytic solution to an efficient algorithm［J］. Physical Review. E， Statistical， Nonlinear， and Soft Matter Physics， 2002， 66（5）： No.056126.
48	KAPORIS A C， KIROUSIS L M， LALAS E G. The probabilistic analysis of a greedy satisfiability algorithm［J］. Random Structures and Algorithms， 2006， 28（4）： 444-480.
49	DÍAZ J， KIROUSIS L， MITSCHE D， et al. On the satisfiability threshold of formulas with three literals per clause［J］. Theoretical Computer Science， 2009， 410（30/31/32）： 2920-2934.
50	DUBOIS O， BOUFKHAD Y， MANDLER J. Typical random 3‑SAT formulae and the satisfiability threshold［C］// Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia， PA： SIAM， 2000： 124-126.
51	KAPORIS A C， KIROUSIS L M， STAMATIOU Y C， et al. Coupon collectors， q-binomial coefficients and the unsatisfiability threshold［C］// Proceedings of the 2001 Italian Conference on Theoretical Computer Science， LNCS 2202. Berlin： Springer， 2001： 328-338.
52	ACHLIOPTAS D， SORKIN G B. Optimal myopic algorithms for random 3-SAT［C］// Proceedings of the 41st Annual Symposium on Foundations of Computer Science. Piscataway： IEEE， 2000： 590-600.
53	KAPORIS A C， KIROUSIS L M， LALAS E. Selecting complementary pairs of literals［J］. Electronic Notes in Discrete Mathematics， 2003， 16： 47-70.
54	FRANZ S， LEONE M. Replica bounds for optimization problems and diluted spin systems［J］. Journal of Statistical Physics， 2003， 111（3/4）： 535-564.
55	MERTENS S， MÉZARD M， ZECCHINA R. Threshold values of random K-SAT from the cavity method［J］. Random Structures and Algorithms， 2006， 28（3）： 340-373.
56	COJA-OGHLAN A， PANAGIOTOU K. The asymptotic k-SAT threshold［J］. Advances in Mathematics， 2016， 288： 985-1068.
57	ACHLIOPTAS D， CHTCHERBA A， ISTRATE G， et al. The phase transition in 1-in-k SAT and NAE 3-SAT［C］// Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete algorithms. Philadelphia， PA： SIAM， 2001： 721-722.
58	COJA-OGLAN A， PANAGIOTOU K. Catching the k-NAESAT threshold［C］// Proceedings of the 44th Annual ACM Symposium on Theory of Computing. New York： ACM， 2012： 899-908.
59	DING J， SLY A， SUN N. Satisfiability threshold for random regular NAE-SAT［J］. Communications in Mathematical Physics， 2016， 341： 435-489.
60	COJA-OGHLAN A. Constraint satisfaction： random regular k-SAT［M］// KRZAKALA F， RICCI-TERSENGHI F， ZDEBOROVA L， et al. Statistical Physics， Optimization， Inference， and Message-Passing Algorithms： Special Issue. Oxford： Oxford University Press， 2015： 231-252.
61	KNYSH S， SMELYANSKIY V N， MORRIS R D. Approximating satisfiability transition by suppressing fluctuations［EB/OL］. ［2023-11-10］. .
62	KALAPALA V， MOORE C. The phase transition in exact cover［J］. Chicago Journal of Theoretical Computer Science， 2008， 2008： No.5.
63	MOORE C. The phase transition in random regular exact cover［J］. Annales de l'Institut Henri Poincaré D， 2016， 3（3）： 349-362.
64	PANAGIOTOU K， PASCH M. Satisfiability thresholds for regular occupation problems［EB/OL］. ［2023-12-05］..
65	DUBOIS O， DEQUEN G. A backbone-search heuristic for efficient solving of hard 3-SAT formulae［C］// Proceedings of the 17th International Joint Conference on Artificial Intelligence. San Francisco： Morgan Kaufmann Publishers Inc， 2001： 248-253.
66	CASTELLANA M， ZDEBOROVÁ L. Adversarial satisfiability problem［J］. Journal of Statistical Mechanics： Theory and Experiment， 2011， 2011（3）： No.P03023.
67	张明明，许道云.正则3-SAT问题的相变现象［J］.计算机科学，2016，43（4）：33-36.
	ZHANG M M， XU D Y. Phase transition phenomenon of regular 3-SAT problem［J］. Computer Science， 2016， 43（4）： 33-36.
68	周锦程，许道云，卢友军.基于1RSB 的正则（k， r）-SAT问题可满足临界［J］.华中科技大学学报（自然科学版），2017，45（12）：7-13.
	ZHOU J C， XU D Y， LU Y J. Satisfiability threshold of regular （k， r）-SAT problem via 1RSB theory［J］. Journal of Huazhong University of Science and Technology （Natural Science Edition）， 2017， 45（12）：7-13.
69	符祖峰，许道云. d-正则（k，s）-SAT问题的NP完全性［J］.软件学报，2020，31（4）：1113-1123.
	FU Z F， XU D Y. NP‑completeness of d-regular （k，s）-SAT problem［J］. Journal of Software， 2020， 31（4）：1113-1123.
70	FU Z， XU D， WANG Y. （1，0）-super solutions of （k，s）-CNF formula［J］. Entropy， 2020， 22（2）： No.253.
71	王永平，许道云.取定s的严格d-正则随机（3，2s）-SAT问题的可满足临界［J］.软件学报，2021，32（9）：2629-2641.
	WANG Y P， XU D Y. Satisfiability threshold of strictly d-regular random（3，2s）-SAT problem for fixed s ［J］. Journal of Software， 2021， 32（9）： 2629-2641.
72	WANG Y P， XU D Y. Satisfiability threshold of the strictly d-regular random （3， s）-SAT problem［C］// Proceedings of the 2020 International Conference on Big Data and Artificial Intelligence and Software Engineering. Piscataway： IEEE， 2020：419-424.

[1]	Linbo HU, Zhiwei NI, Jiale CHENG, Wentao LIU, Xuhui ZHU. Collaborative crowdsourcing task allocation method fusing community detection [J]. Journal of Computer Applications, 2025, 45(2): 534-545.
[2]	Qianting ZHANG, Liying HU, Lifei CHEN. Robust shapelet representation method for time series [J]. Journal of Computer Applications, 2025, 45(2): 436-443.
[3]	. Design and practice of intelligent tutoring algorithm based on personalized emotional awareness [J]. Journal of Computer Applications, 0, (): 0-0.
[4]	Quan TANG, Peng WANG, Gang XIN. Optimization algorithm entropy based on quantum dynamics [J]. Journal of Computer Applications, 2025, 45(1): 186-195.
[5]	. YOLOv5s-MRD: an efficient fire and smoke detection algorithm for complex scenarios based on YOLOv5s [J]. Journal of Computer Applications, 0, (): 0-0.
[6]	Yanfei WANG, Peng ZHANG, Xiangguang DAI, Huijun LI. Fixed-time time-varying algorithm applied to robot navigation problem [J]. Journal of Computer Applications, 0, (): 154-158.
[7]	Yang CAO, Zhaoyang WU. Differential evolution algorithm based on multi-population adaptation and historically successful parameters [J]. Journal of Computer Applications, 0, (): 134-138.
[8]	Qiye ZHANG, Xinrui ZENG. Efficient active-set method for support vector data description problem with Gaussian kernel [J]. Journal of Computer Applications, 2024, 44(12): 3808-3814.
[9]	. Path planning of multi-UAV formation based on improved artificial potential field method [J]. Journal of Computer Applications, 0, (): 0-0.
[10]	. Dual-population dual-stage evolutionary algorithm for complex constrained multi-objective optimization problems [J]. Journal of Computer Applications, 0, (): 0-0.
[11]	Qin LENG, Zhengyuan MAO. Two echelon location-routing optimization considering facility sizing decision [J]. Journal of Computer Applications, 2024, 44(11): 3513-3520.
[12]	Renke SUN, Zhiyu HUANGFU, Hu CHEN, Zhongnian LI, Xinzheng XU. Survey of neural architecture search [J]. Journal of Computer Applications, 2024, 44(10): 2983-2994.
[13]	Antai SUN, Ye LIU, Dongmei XU. Dynamic surface asymptotic compensation algorithm for multi-agent systems [J]. Journal of Computer Applications, 2024, 44(10): 3151-3157.
[14]	Chaoying YAN, Ziyi ZHANG, Yingnan QU, Qiuyu LI, Dixiang ZHENG, Lijun SUN. Double auction carbon trading based on consortium blockchain [J]. Journal of Computer Applications, 2024, 44(10): 3240-3245.
[15]	. Dung beetle optimizer algorithm with restricted reverse learning and Cauchy-Gauss variation [J]. Journal of Computer Applications, 0, (): 0-0.

Review of phase transition in satisfiability problems

可满足性问题相变研究综述

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 72

Related Articles 15

Recommended Articles

Metrics