The complexity of the satisfiability problem for Krom formulas |
| |
| Authors: | Larry Denenberg Harry R. Lewis |
| |
| Affiliation: | Aiken Computation Laboratory 102, Harvard University, Cambridge, MA 02138, U.S.A. |
| |
| Abstract: | We study the computational complexity of the satisfiability problem for Krom (CNF-2) formulas. Upper and lower bounds are obtained for several decidable classes of formulas determined by quantifier prefix and degree of predicate letters. For example, we show that determining satisfiability of Krom formulas with quantifier prefix of the form ……… is complete for deterministic exponential time, but that if the number of universal quantifiers is bounded then polynomial time suffices. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
