华中科技大学学报（自然科学版）2025，Vol.53Issue(10)：42-48,83,8.DOI:10.13245/j.hust.251098
随机正则3-(d,k)-SAT问题的可满足性相变
Satisfiable phase transition in random regular 3-(d,k)-SAT problem
摘要
Abstract
Let d denote the variable occurrence count and k denote the clause length.Inspired by the characteristics of the random regular exact(d,k)-SAT problem,the random regular 3-(d,k)-SAT problem was proposed.First,an instance generation model for the random regular 3-(d,k)-SAT problem was introduced to generate random regular(d,k)-CNF formulas.The model employed perfect matching mechanism,where each random perfect matching corresponded to a random regular 3-(d,k)-SAT instance.Then,combined with the first moment method,the second moment method,and the solution space structure of the regular(d,k)-CNF formula,the satisfiability phase transition point dk in the random regular 3-(d,k)-SAT problem was given for k＞3.When d＞dk,the random regular(d,k)-CNF instance formulas were 3-exactly unsatisfiable with high probability;when d＜dk,the random regular(d,k)-CNF instance formulas were 3-exactly satisfiable with high probability.Finally,the experiments were conducted on two datasets with n=10,k=6 and n=15,k=10.Experimental results show that the random regular 3-(d,k)-SAT problem exhibits phase transition phenomenon,which occurs around d6=1.407 4 and d10=1.962 4,respectively,verifying the correctness of the phase transition points obtained from the theoretical proofs.关键词
相变现象/随机正则3-(d,k)-SAT问题/矩方法/正则(d,k)-CNF公式/生成模型Key words
phase transition phenomena/random regular 3-(d,k)-SAT problem/moment method/regular(d,k)-CNF formula/generation model分类
计算机与自动化引用本文复制引用
王晓峰,唐傲,彭庆媛,颜冬,华盈盈,何飞,王军霞..随机正则3-(d,k)-SAT问题的可满足性相变[J].华中科技大学学报（自然科学版）,2025,53(10):42-48,83,8.基金项目
国家自然科学基金资助项目(62062001) （62062001）
宁夏自然科学基金资助项目(2024AAC03165,2024AAC03169) （2024AAC03165,2024AAC03169）
宁夏青年拔尖人才资助项目 （）
北方民族大学研究生创新项目(YCX24121). （YCX24121）
