Satisfiability Threshold of the Regular Random (k,r)-SAT Problem
Author:
Affiliation:

Clc Number:

Fund Project:

National Natural Science Foundation of China (61262006, 61463044, 61462001); Science and Technology Foundation of Guizhou Province of China (LKQS201313)

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    This article studies the strictly regular (k,r)-SAT problem by restricting the k-SAT problem instances, where each variables occurs precisely r=2s times and each of the positive and negative literals occurs precisely s times. By constructing a special independent random experiment, the study derives an upper bound on the satisfiability threshold of the strictly regular random (k,r)-SAT problem via the first moment method. Based on the fact that the satisfiability threshold of the strictly regular and the regular random (k,r)-SAT problems are approximately equal, a new upper bound on the threshold of the regular random (k,r)-SAT problem is obtained. This new upper bound is not only below the current best known upper bounds on the satisfiability threshold of the regular random (k,r)-SAT problem, but also below the satisfiability threshold of the uniform random k-SAT problem. Thus, it is theoretically explained that in general the regular random (k,r)-SAT instances are harder to satisfy at their phase transition points than the uniform random k-SAT problem at the corresponding phase transition points with same scales. Finally, numerical results verify the validity of our new upper bound.

    Reference
    Related
    Cited by
Get Citation

周锦程,许道云,卢友军.随机正则(k, r)-SAT问题的可满足临界.软件学报,2016,27(12):2985-2993

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:July 05,2016
  • Revised:
  • Adopted:
  • Online: October 19,2016
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063