AbstractIn propositional logic, several problems, such as satisfiability, MAX SAT and logical inference, can be formulated as integer programs. In this paper, we consider sets of clauses for which the corresponding integer programs can be solved as linear programs. We prove that balanced sets of clauses have this property. Copyright 1995 by ACM, Inc.
The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- computations on discrete structures; G.2.1 [Discrete Mathematics]: Combinatorics -- combinatorial algorithms
General Terms: Algorithms
Additional Key Words and Phrases: Balanced matrices, linear programming, propositional logic
Selected references
- V. Chandru and J. N. Hooker. Extended Horn sets in propositional logic. Journal of the ACM, 38(1):205-221, January 1991.