On the complexity of the maximum satisfiability problem for Horn formulas
From MaRDI portal
Publication:1099168
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
NP-completenessexpert systemslogic programmingmaximum satisfiabilityHorn formulaspartial consistency of logic databases
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
