The complexity of the satisfiability problem for Krom formulas

DOI10.1016/0304-3975(84)90138-5zbMath0552.03023OpenAlexW2007102962MaRDI QIDQ800915

Larry Denenberg, Harry R. Lewis

Publication date: 1984

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(84)90138-5

zbMATH Keywords

satisfiability problemKrom formula

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15)

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity results for classes of quantificational formulas
• Complete problems for deterministic polynomial time
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• ENTSCHEIDUNGSPROBLEM REDUCED TO THE AEA CASE
• On the sequential nature of unification
• On the complexity of integer programming
• Alternation
• Prefix classes of Krom formulas
• Resolution Strategies as Decision Procedures
• New problems complete for nondeterministic log space
• Bounded Algol-Like Languages