Satisfiability problems for propositional calculi
Satisfiability problems for propositional calculi
复制标题
命题计算的可满足性问题
DOI：
10.1007/bf01744287
复制
发表时间：
1979
期刊：
影响因子：
--
通讯作者：
H. R. Lewis
中科院分区：
文献类型：
--
作者：
H. R. Lewis
对于每个固定的布尔连接词集合，确定仅包含这些连接词的公式的可满足性有多难？我们证明了NP-完备性的一个充分条件是函数xΛ~y是可表示的，并且任何不能表示该函数的连接词集合都存在多项式时间可满足性问题。
For each fixed set of Boolean connectives, how hard is it to determine satisfiability for formulas with only those connectives? We show that a condition sufficient for NP-completeness is that the functionx Λ ~ y be representable, and that any set of connectives not capable of representing this function has a polynomial-time satisfiability problem.