NP-completeness of d-regular (k,s)-SAT Problem
Author:
Affiliation:

Clc Number:

TP301

Fund Project:

National Natural Science Foundation of China (61762019, 61862051)

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

    The study on the NP-completeness of regular SAT problem is a subject which has important theoretical value. It is proved that there is a critical function f(k) such that all formulas in (k,f(k))-CNF are satisfiable, but (k,f(k)+1)-SAT is NP-complete, and there is such a critical function about regular (k,s)-SAT problem too. This work studies the regular SAT problem with stronger regular constraints. The regular (k,s)-CNF is the subclass of CNF in which each clause of formula has exactly k distinct literals and each variable occurs exactly s times. The d-regular (k,s)-CNF is a regular (k,s)-CNF formula that the absolute value of the difference between positive and negative occurrence number of each variable in the formula is at most d. A polynomial reduction from a k-CNF formula is presented to a d-regular (k,s)-CNF formula and it is proved that there is a critical function f(k,d) such that all formulas in d-regular (k,f(k,d))-CNF are satisfiable, but d-regular (k,f(k,d)+1)-SAT is already NP-complete. By adding new variables and new clauses, the reduction method not only can alter the ration of clauses to variables of any one CNF formula, but also can restrict the difference between positive and negative occurrences number of each variable. This shows that only using constrained density (the ration of clauses to variables) to character structural features of a CNF formula is not enough. The study of the critical function f(k,d) is helpful to construct some hard instance under stronger regular constraints.

    Reference
    Related
    Cited by
Get Citation

符祖峰,许道云.d-正则(k,s)-SAT问题的NP完全性.软件学报,2020,31(4):1113-1123

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:April 24,2019
  • Revised:November 03,2019
  • Adopted:
  • Online: April 16,2020
  • Published: April 06,2020
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