Artificial Intelligence Stack Exchange is a question and answer site for people interested in conceptual questions about life and challenges in a world where "cognitive" functions can be mimicked in purely digital environment. It only takes a minute to sign up.
Sign up to join this community
I have taken an algorithms course where we talked about LP significantly, and also many reductions to LPs. As I recall, normal LP is not NP-Hard. Integer LP is NP-Hard. I am currently taking an introduction to AI course, and I was wondering if CSP is the same as LP.
There seems an awful lot of overlap, and I haven't been able to find anything that confirms or denies my suspicions.
If they are not the same (or one cannot be reduced to the other), what are the core differences in their concepts?
LP is a mathematical problem to optimize a linear function subject to linear (in)equality constraints of the sort: $$ min_x w^t x $$ $$ Ax<b $$
where $x$ is a continuous variable (vector). If the problem is feasible, then a unique global optimal solution exists for $x$
A constraint satisfaction problem on the other hand is just the constraints part of the above LP. So we are not interested in the optimal solution, just a set of values that will satisfy the constraints. If the domain of your variables is continuous, then it can be recast as a dummy LP with a fake objective e.g. $min_x 0, s.t. Ax<b$, and then solved with an LP solver (e.g. simplex algorithm)
However many CSPs have discrete variables so they are not LP. Also CSP problems may have too many variables for plain LP algorithms to handle, so there are problem specific shortcut algorithms. We are often happy to find a feasible solution and forget about "optimality"
