The inequality-satisfiability problem

The inequality-satisfiability problem

0.00 Avg rating0 Votes
Article ID: iaor20091367
Country: Netherlands
Volume: 36
Issue: 2
Start Page Number: 229
End Page Number: 233
Publication Date: Mar 2008
Journal: Operations Research Letters
Authors: ,
Keywords: satisfiability
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.

Reviews

Required fields are marked *. Your email address will not be published.