# If a CSP (over a finite domain) has only linear inequalities as constraints, is it solvable in linear time?

I have an optimization problem in fuzzy logic that I want to model and solve as a CSP. If I could use only linear inequalities in my encoding, is the resulting CSP solvable in linear time?

Problem statement: Given a set of formulas in CNF in Łukasiewicz logic, I want to find an assignment for the variables in some truth set T_k, for some k, such that the assignment maximizes the number of satisfied formulas. I wanted to model this problem into CSP or SAT, hence my question. The SAT problem for CNF Łukasiewicz logic formulas is solvable in linear time. So, maybe we can take advantage of that.

## 1 Answer

Probably not, since clauses can be encoded using only linear inequalities.
http://web.stanford.edu/~rrwill/cnf-sat-feasible.pdf

• In some cases where the constraints are linear it can be solved in polynomial time using linear programming. My problem is understanding those cases. – Halaby Jan 31 '16 at 9:12
• Since your domain is finite and hence discrete, you are essentially dealing with integer linear programming, which is not known to be in P. – Klaus Draeger Jan 31 '16 at 12:27
• Are there some cases where it is solvable in polynomial time? – Halaby Jan 31 '16 at 13:27