k-LSAT is NP-Complete for k≥3
DOI:
Author:
Affiliation:

Clc Number:

Fund Project:

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

    A CNF formula F is linear if any distinct clauses in F contain at most one common variable.A CNF formula F is exact linear if any distinet clauses in F contain exactly one conlrnon vailable.All exact linear formulas are satisfiable[1],and for the class LCNF of linear formulas,the decision problem LSAT remains NP-complete.For the subclasses LCNFkof LCNF,in which formulas have only clauses of length at least k,the NP-completeness of the decision problem LSATkis closely relevant to whether or not there exists an unsatisfiable formula in LCNFk,i.e.,the NP-eompletness of SAT for LCNFk(k≥3)is the question whether there exists an unsatisfiable formula in LCNFk.S.Porschen et al.have shown that both LCNF3and LCNF4contain unsatisfiable formulas by the constructions of hypergraphs and latin squares.It leaves the open question whether for each k≥5 there is an unsatisfiable formula in LCNFk.This paper presents a simple and general method to construct unsatisfiable formulas in k-LCNF for each k≥3 by the application of minimal unsatisfiable formulas to reductions for formulas.It is shown that for each k≥3 there exists a minimal unsatisfiable formula in k-LCNF.Therefore,the stronger result is shown that k-LSAT is NP-complete for k≥3.

    Reference
    Related
    Cited by
Get Citation

许道云,邓天炎,张庆顺.k-LSAT (k≥3)是NP-完全的.软件学报,2008,19(3):511-521

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:December 13,2006
  • Revised:January 24,2007
  • Adopted:
  • Online:
  • 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