%0 Journal Article
%T k-LSAT is NP-Complete for k≥3<br>k-LSAT(k≥3)是NP-完全的
%A XU Dao-Yun
%A DENG Tian-Yan
%A ZHANG Qing-Shun
%A <br>许道云
%A 邓天炎
%A 张庆顺
%J 软件学报
%D 2008
%I 
%X 合取范式(conjunctive normal form,简称CNF)公式F是线性公式,如果F中任意两个不同子句至多有一个公共变元.如果F中的任意两个不同子句恰好含有一个公共变元,则称F是严格线性的.所有的严格线性公式均是可满足的,而对于线性公式类LCNF,对应的判定问题LSAT仍然是NP-完全的.LCNF≥k是子句长度大于或等于k的CNF公式子类,判定问题LSA(≥k)的NP-完全性与LCNF(≥k)中是否含有不可满足公式密切相关.即LSAT≥k的NP-完全性取决于LCNF≥k是否含有不可满足公式.S.Porschen等人用超图和拉丁方的方法构造了LCNF≥3和LCNF≥4中的不可满足公式,并提出公开问题:对于k≥5,LCNF≥k是否含有不可满足公式?将极小不可满足公式应用于公式的归约,引入了一个简单的一般构造方法.证明了对于k≥3,k-LCNF含有不可满足公式,从而证明了一个更强的结果:对于k≥3,k-LSAT是NP-完全的.
%K linear CNF formula
%K unsatisfiability
%K NP-completeness
%K minimal unsatisfiable formula
%K reduction<br>线性CNF公式
%K 不可满足性
%K NP-完全性
%K 极小不可满足公式
%K 归约
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=5881E24B0EE3133344803D0433CBA60C&yid=67289AFF6305E306&vid=2A8D03AD8076A2E3&iid=38B194292C032A66&sid=B99A53AADE50D922&eid=68FF5306A8F9C315&journal_id=1000-9825&journal_name=软件学报&referenced_num=0&reference_num=11