A hierarchy of propositional Horn formuls

DOI10.1016/0304-3975(89)90123-0zbMath0676.03026OpenAlexW2030000722MaRDI QIDQ1122571

Bogdan S. Chlebus

Publication date: 1989

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

Full work available at URL: https://doi.org/10.1016/0304-3975(89)90123-0

zbMATH Keywords

bounded- depth circuitshierarchy of propositional Horn formulasnumber of alternations between players in a gamesatisfiability of Horn formulas

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Classical propositional logic (03B05)

Cites Work

• Some simplified NP-complete graph problems
• Complete problems for deterministic polynomial time
• On the unique satisfiability problem
• Nondeterministic Space is Closed under Complementation
• Satisfiability problems for propositional calculi
• Alternation
• On the Complexity of Timetable and Multicommodity Flow Problems
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A hierarchy of propositional Horn formuls