Satisfiability problems for propositional calculi |
| |
Authors: | Harry R Lewis |
| |
Affiliation: | (1) Aiken Computation Laboratory, Harvard University, 02138 Cambridge, Massachusetts, USA |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|