On the complexity of the maximum satisfiability problem for Horn formulas

DOI10.1016/0020-0190(87)90028-7zbMath0638.03036OpenAlexW2083756938MaRDI QIDQ1099168

Bruno Simeone, Brigitte Jaumard

Publication date: 1987

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(87)90028-7

zbMATH Keywords

NP-completenessexpert systemslogic programmingmaximum satisfiabilityHorn formulaspartial consistency of logic databases

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity of proofs (03F20)

Related Items

On Tackling Explanation Redundancy in Decision Trees, A simplified NP-complete MAXSAT problem, Complexity versus stability for classes of propositional formulas, Resolution and the integrality of satisfiability problems, Max Horn SAT and the minimum cut problem in directed hypergraphs, Probabilistic bounds and algorithms for the maximum satisfiability problem, Extending time‐to‐target plots to multiple instances, Extensions of unification modulo ACUI, Propositional proof systems based on maximum satisfiability, Probability logic and optimization SAT: The PSAT and CPA models, Directed hypergraphs and applications, Algorithms for the maximum satisfiability problem, Voting on multi-issue domains with conditionally lexicographic preferences, On the complexity of inconsistency measurement, Syntactic expressions to express NP-hard optimization problems and problems with zero duality gap

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some simplified NP-complete graph problems
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Minimum cuts and related problems
• Network Flow and Testing Graph Connectivity
• The complexity of theorem-proving procedures