4 ms·
It's easy to formulate 3-SAT as an LP feasibility problem. The problem is that you need solutions in which all variables are either 0 or 1. That makes it an i
by tgflynn 11y ago
It's easy to formulate 3-SAT as an LP feasibility problem. The problem is that you need solutions in which all variables are either 0 or 1. That makes it an integer or 0-1 LP problem and such problems are NP hard.
- schoen 11y agoI don't know if there's ultimately an analogy in the deeper mathematical structure, but the difference between the logarithm problem and the discrete logarithm problem comes to mind. On the one hand, in both cases it's "just" finding the inverse of an operation over a field. On the other hand, numerical approximations of continuous logarithms are straightforward and quick to calculate, yet discrete logarithms aren't.
- tgflynn 11y agoI'm not very familiar with the discrete logarithm problem but it seems to be fairly generally true that many problems which are easy in the continuous case become hard when you try to restrict the solutions to a grid. Even solving the linear equation Ax = b in n dimensions, I believe, is NP hard for x \in {0,1}^n.
- schoen 11y agoI wonder if we could say that this has to do with the integers having measure zero in the reals, so if you want to actually hit them you may need a qualitatively better kind of "aim". (I don't know enough higher math to know if this intuition is meaningful or not.)
- tgflynn 11y agoThere are probably a lot of different ways to look at it. One perspective is that easy problems usually involve convex sets (or minimizing convex functions, which is pretty much the same thing since the solution set is guaranteed to be convex). Discrete sets, such as the vertex set of a hypercube, are trivially non-convex (unless they only contain a single element). You can also think about it geometrically. Imagine you have a plane that passes through a cube. How do you determine if it intersects one of the cube vertices (this is basically equivalent to the subset sum problem) ? Of course it's easy to find a method that will work in 3D, but these methods all end up scaling exponentially with the dimension of the space.
- guilamu 11y agoThanks a lot for your comment, I hope this will help Feldmann.