| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1142917 | Operations Research Letters | 2008 | 5 Pages |
Abstract
We define a generalization of the satisfiability problem (SAT) where each “clause” is an or-list of inequalities in n variables. This problem is NP-complete even when containing only two inequalities per “clause”, but solvable in polynomial time when either the number of variables or the number of “clauses” is fixed.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Dorit S. Hochbaum, Erick Moreno-Centeno,