On the upper bounds of (1,0)-super solutions for the regular balanced random (k,2s)-SAT problem  

作　　者：Yongping WANG Daoyun XU Jincheng ZHOU 

机构地区：[1]School of Information,Guizhou University of Finance and Economics,Guiyang 550025,China [2]College of Computer Science and Technology,Guizhou University,Guiyang 550025,China [3]School of Computer and Information,Qiannan Normal University for Nationalities,Duyun 558000,China [4]Key Laboratory of Complex Systems and Intelligent Optimization of Guizhou Province,Duyun 558000,China

出　　处：《Frontiers of Computer Science》2024年第4期139-146,共8页中国计算机科学前沿（英文版）

基　　金：Scientific Research Project for Introduced Talents of Guizhou University of Finance and Economics(No.2021YJ007);National Natural Science Foundation of China(Grant Nos.61862051,61762019,62241206);Top-notch Talent Program of Guizhou Province(No.KY[2018]080);Science and Technology Foundation of Guizhou Province(No.20191299);foundation of Qiannan Normal University for Nationalities(Nos.QNSYRC201715,QNSY2018JS013).

摘　　要：This paper explores the conditions which make a regular balancedrandom(k,2s)-CNFformula(1,O)-unsatisfiable with high probability.The conditions also make a random instance of the regular balanced(k-1,2(k-1)s)-SAT problem unsatisfiable with high probability,where the instance obeys a distribution which differs from the distribution obeyed by a regular balanced random(k-1,2(k-1)s)-CNF formula.Let F be a regular balanced random(k,2s)-CNF formula where k≥3,then there exists a number so such that F is(1,O)-unsatisfiable with high probability if s>so.A numerical solution of the number so when k e(5,6,...,14)is given to conduct simulated experiments.The simulated experiments verify the theoretical result.Besides,the experiments also suggest that F is(1,O)-satisfiable with high probability if s is less than a certain value.

关 键 词：regular balanced random(k 2s)-SAT problem (1 0)-super solution upper bound 

分 类 号：O211.6[理学—概率论与数理统计]