论文部分内容阅读
合取范式（conjunctive normal form，简称CNF）公式F是线性公式，如果F中任意两个不同子句至多有一个公共变元．如果F中的任意两个不同子句恰好含有一个公共变元，则称F是严格线性的．所有的严格线性公式均是可满足的，而对于线性公式类LCNF,对应的判定问题LSAT仍然是NP-完全的．LCNF≥k是子句长度大于或等于后的CNF公式子类，判定问题LSAT≥k的NP-完全性与LCNF≥k中是否含有不可满足公式密切相关．即LSAT≥k的NP-完全性取决于LCNF≥k是否含有不可满足公式．S．Por