Title :
A class of logic problems solvable by linear programming
Author :
Conforti, Michele ; Cornuéjols, Gérard
Author_Institution :
Dipartmento di Matematica, Padova Univ., Italy
Abstract :
Several problems of propositional logic, such as satisfiability, MAXSAT and logical inference, can be formulated as integer programs. The authors consider sets of clauses for which these integer programs can be solved as linear programs. They prove that balanced sets of clauses have this property
Keywords :
computability; formal logic; inference mechanisms; integer programming; MAXSAT; balanced sets of clauses; integer programs; linear programming; logic problems; logical inference; propositional logic; satisfiability; truth assignment; Linear matrix inequalities; Linear programming; Logic programming; Polynomials; Sufficient conditions;
Conference_Titel :
Foundations of Computer Science, 1992. Proceedings., 33rd Annual Symposium on
Conference_Location :
Pittsburgh, PA
Print_ISBN :
0-8186-2900-2
DOI :
10.1109/SFCS.1992.267784
