%0 Journal Article
%T k-lsat(k≥3)是np-完全的
%A 许道云？
%A 邓天炎？
%A 张庆顺？
%J 软件学报
%P 511-521
%D 2008
%X 合取范式(conjunctivenormalform,简称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 线性cnf公式
%K 不可满足性
%K np-完全性
%K 极小不可满足公式
%K 归约
%U http://www.jos.org.cn/ch/reader/view_abstract.aspx?file_no=20080304&flag=1