In my computer science education, I increasingly notice that most discrete problems are NP-complete (at least), whereas optimizing continuous problems is almost always easily achievable, usually through gradient techniques. Are there exceptions to this?
$\begingroup$
$\endgroup$
7
-
14$\begingroup$ There surely are, many of them. Bipartite and general matching, and min cuts are three classical polynomial time solvable discrete problems. Many continuous non-convex optimization problems are NP-hard: finding the diameter of a convex set, or computing the injective norm of a 3-d tensor. $\endgroup$– Sasho NikolovApr 7, 2015 at 20:44
-
6$\begingroup$ Here is a simple continuous optimisation problem that is NP-hard to solve: cstheory.stackexchange.com/questions/14630/… $\endgroup$– Jukka SuomelaApr 7, 2015 at 21:52
-
8$\begingroup$ I'm not sure what problems you have in mind, but many continuous problems that are "solved" by gradient methods aren't really "solved": the method merely finds some kind of local optimum. $\endgroup$– Suresh VenkatApr 8, 2015 at 4:24
-
1$\begingroup$ All the responses so far seem to be counterexamples, but it would be nice to see some cases where this rule does seem to hold true. Two that come to mind are linear programming vs integer programming and convex optimization vs submodular maximization. $\endgroup$– usulApr 8, 2015 at 14:40
-
13$\begingroup$ I think the whole discrete vs continuous thing is a red herring. A problem has to have very special structure to be efficiently solvable. I think the real difference here is that in the case of easy continuous problems the special structure tends to be convexity, while in the case of easy discrete problems things look more complicated: sometimes the structure is submodularity or matroid intersection, but often it's not. This probably has more to do with the fact that we don't yet understand discrete math very well. $\endgroup$– Sasho NikolovApr 9, 2015 at 0:04
|
Show 2 more comments
5 Answers
$\begingroup$
$\endgroup$
4
An example that I love is the problem where, given distinct $a_1, a_2, \ldots, a_n \in \mathbb{N}$, decide if: $$\int_{-\pi}^{\pi} \cos(a_1 z) \cos(a_2 z) \ldots \cos(a_n z) \, dz \ne 0$$
This at first seems like a continuous problem to evaluate this integral, however it is easy to show that this integral is not zero iff there exists a balanced partition of the set $\{a_1, \ldots, a_n\}$, so this integral problem is actually NP-complete.
Of course, I encourage playing around with some numerical tools to convince yourself that most (if not all) numerical tricks to evaluate this integral are doomed to failure once $n$ gets large enough.
-
4$\begingroup$ Since we're on the topic, the earliest reference to this problem I can find is in "The Nature of Computation" by Moore and Mertens. They provide no reference, so I assume either they invented it, or it comes from folklore. I would appreciate if someone knows the source of this problem. $\endgroup$ Apr 8, 2015 at 1:31
-
$\begingroup$ Presumably not only most but all numerical techniques will scale catastrophically for large enough $n$? Since the problem is NP-complete, an accurate numerical technique for evaluating that integral that scaled polynomially in $n$ would be enough to show P=NP. $\endgroup$– E.P.Apr 8, 2015 at 19:28
-
1$\begingroup$ Right, an algorithm that always evaluates that integral correctly in time polynomial in $n$ would be sufficient to show P=NP. On the other hand, I can't 100% rule out the possibility of certain numerical techniques that I'm not aware of somehow doing well on specific instances of this integral, even when $n$ is large, much like how SAT solvers are often able to find satisfying assignments for some formulae with thousands of variables, even though the worst-case performance is bad. So, even if I doubt such methods exist, I hedged my answer a little bit. $\endgroup$ Apr 8, 2015 at 21:10
-
3$\begingroup$ Apparently the original source of this problem is: David Plaisted, Some polynomial and integer divisibility problems are NP-hard. SIAM Journal on Computing, 7 (4):458–464, 1978. The reference is in the rear of Moore and Mertens, just not in the body of text itself. $\endgroup$ Apr 12, 2015 at 6:15
$\begingroup$
$\endgroup$
1
There are many continuous problems of the form "test whether this combinatorial input can be realized as a geometric structure" that are complete for the existential theory of the reals, a continuous analogue of NP. In particular, this implies that these problems are NP-hard rather than polynomially solvable. Examples include testing whether a given graph is a unit distance graph, whether a given graph can be drawn in the plane with straight line segment edges and at most a given number of crossings, or whether a given pseudoline arrangement can be stretched to form a line arrangement.
There are other continuous problems that are even harder: for instance, finding a shortest path among polyhedral obstacles in 3d is PSPACE-complete (Canny & Reif, FOCS'87).
answered Apr 7, 2015 at 22:42
-
1$\begingroup$ 'Shortest path among polyhedral obstacles' is continuous in name only, isn't it? We can think of the configuration space as a union of a number of discrete pieces corresponding to paths that 'hug' a given set of obstacles; then local optimization within each given piece (i.e., within any given set of obstacles) is straightforward but deciding which of the paths has the globally-best distance is the hard part of the problem. $\endgroup$ Apr 12, 2015 at 22:31
$\begingroup$
$\endgroup$
2
While this doesn't exactly answer your original question, it's a (conjectural) example of a sort of philosophical counterpoint: a problem where the presentation is discrete but all of the hardness comes from the 'continuous' aspect of the problem.
The problem is the Sum of Square Roots problem: given two sets of integers $A=\{a_1, a_2, \ldots, a_m\}$ and $B=\{b_1, b_2, \ldots, b_n\}$, is $\sum_{i=1}^m \sqrt{a_i}\leq\sum_{j=1}^n\sqrt{b_j}$? (There are other formulations, but this is the one I prefer.) While it's not known for certain to be hard, it's widely suspected that it may be NP-hard and may in fact be outside of NP (there are, as noted in the comments, excellent reasons to believe that it's not NP-complete); the only containment known to date is several levels higher up the polynomial hierarchy. Obviously the presentation of this problem is as discrete as can be — a set of integers and a yes/no question about them — but the challenge arises because while computing square roots to any specified precision is an easy problem, they may need to be computed to high (potentially superpolynomial) accuracy to settle the inequality one way or the other. This is a 'discrete' problem that crops up in a surprising number of optimization contexts and helps contribute to their own complexity.
answered Apr 12, 2015 at 22:43
-
4$\begingroup$ I like this example a lot too, though it is worth pointing out that there are strong reasons to believe it's not NP-complete; see (cstheory.stackexchange.com/a/4010/8985) $\endgroup$ Apr 13, 2015 at 0:26
-
$\begingroup$ @JoeBebel Very good point - I've revised my language slightly to reflect that. Thank you! $\endgroup$ Apr 15, 2015 at 17:09
$\begingroup$
$\endgroup$
8
Discrete problems typically tend to be harder (e.g. LP vs. ILP) but it's not the discreteness itself that's the problem... it's how the constraints affect how you can search your domain. For example, you may think that optimizing a polynomial is something that you can do efficiently, but deciding convexity of quartics (degree-4 polynomials) is NP-hard.
Which means even if you already have the optimum somehow, simply proving that you are at the optimum is already NP-hard.
-
$\begingroup$ I think the discreteness is also part of the problem. Say for instance you would have an ILP varant of LP. You can for instance aim to find the solution for the LP variant, but then there are still
2^n"interesting neighbors" you need to search for. $\endgroup$ Apr 8, 2015 at 18:35 -
$\begingroup$ @CommuSoft: Not really... the discreteness isn't the issue. Check out the shortest path problem, which is a discrete problem but nevertheless reduces to a special case of integral linear programming, which is P-time solvable (not to be confused with integer linear programming, which is obviously NP-hard). $\endgroup$ Apr 8, 2015 at 18:36
-
$\begingroup$ that's not really a surprise: since integer linear programming is NP-complete, every problem in P (that can be solved in poly time), can be transformed in poly time in an ILP problem. $\endgroup$ Apr 8, 2015 at 18:39
-
$\begingroup$ @CommuSoft: Did you read the comment fully? I'm not talking about ILP. $\endgroup$ Apr 8, 2015 at 18:39
-
$\begingroup$ sorry, read to fast. But still that's because the constraints are total unimodular, so only by the "grace" of well structured constraints, such problems are easy solvable. In general discretization is a problematic aspect in problems. $\endgroup$ Apr 8, 2015 at 18:42
$\begingroup$
$\endgroup$
8
Although for some popular problems, it is indeed true, I think both assumptions are - depending on what you define as an optimization problem - not true.
First some definitions: most optimization problems are not part of NP. For instance for the Knapsack problem: one cannot exploit non-determinism to construct the most valuable bag, simple because the different non-deterministic branches have no shared memory. NP is also defined as "polynomially verifiable" (verifying a certificate) [1, p. 34]. In this case the certificate is for instance a bag: a bitstring where if the i-th bit is set, it implies the i-th item is part of the bag. You can indeed check in polynomial time if such bag is more valuable than a given threshold (this is the decision variant), but you cannot - as far as we know - based on a single bag, (a polynomial number of bags), decide if that bag is the most valuable of all possible bags. That's a vital difference between for instance NP and EXP: in EXP, you can enumerate over all possible bags and do bookkeeping about which bag is the best one.
The decision variant of the optimization problems is in some cases part of NP, one needs to make a clear distinction between the maximization flavor and the decision flavor. In the decision flavor, the question is: "Given an optimization problem, and a utility bound, is there a solution with a utility greater than or equal to that bound" (or slightly modified for a minimization problem).
I also assume that by NP you mean the (hypothetical) part of NP that is not part of P. If P=NP, of course NP-complete still exists, but it will be equal to P (only coincides with P for some notions of reduction, like polynomial-time many-one reductions by @AndrásSalamon), which is not that impressive (and would reduce the "gap" you are stating in your question).
I increasingly notice that most discrete problems are NP-complete.
Now that we have sorted that out: there are a lot of optimization problems that are in P: shortest path problem, maximum flow problem (for integral capacities), minimum spanning tree and maximum matching. Although these problems may look "trivial to solve" to you, these are still optimization problems, and in many cases the construction (and prove of correctness) is not that easy. So the claim doesn't hold all discrete problems are NP-complete. Given P is not equal to NP, these problems thus can't be NP-complete.
One can furthermore walk through the polynomial hierarchy, this hierarchy provides a way to construct a decision problem that is in $\Sigma^P_i$, but given a decision problem, you can (nearly) always construct an optimization problem that is at least as hard (if the optimization variant was less hard, one could solve the decision variant by calling the optimization variant first, and then make a decision based on the result of that algorithm).
Whereas optimizing continuous problems is almost always easily achievable.
A popular continuous problem that is NP-hard is quadratic programming.
In quadratic programming, one is looking for a vector $\vec{x}$ such that:
$$\dfrac{\vec{x}^T\cdot Q\cdot\vec{x}}{2}+\vec{c}^T\cdot\vec{x}$$ is minimized satisfying:
$$A\cdot\vec{x}\leq\vec{b}$$
Actually Linear programming has long been considered NP-hard as well, but with very well performing heuristics (the Simplex method). Karmarkar's algorithm is however in P.
From the moment the optimization problem deals with non-convex objects, in general it will be hard - if not impossible - to find an efficient algorithm.
Bibliography
[1] Computational Complexity, a modern approach, Sanjeev Arora and Boaz Barak
-
2$\begingroup$ The definitions paragraph is indeed sort of confused. Knapsack is an NP optimization problem. It is not true that "it is not known" if the optimization version is in NP: it is not, simply by definition. Also I don't think we know any problem which is NP-complete conditional on NP not equal to P. I.e. 3-SAT will be NP-complete even if P = NP (actually if P = NP every problem in P is NP complete). $\endgroup$ Apr 8, 2015 at 7:47
-
$\begingroup$ @AndrásSalamon: point taken. I removed that part. It was indeed a bit sloppy. $\endgroup$ Apr 8, 2015 at 7:50
-
$\begingroup$ @AndrásSalamon: evidently that's true. Therefore it says: "Given P is not equal to NP, these problems thus can't be NP-complete." $\endgroup$ Apr 8, 2015 at 15:29
-
$\begingroup$ @AndrásSalamon: Well if
P=NP, every problem in NP-complete is by definition part of NP and thus by extend P, now P means there is a polynomial algorithm. The point is, I think the transformation doesn't matter, because for every language in P there must exist a polynomial algorithm. Whether you take the (at most polynomial) transformation or not, is irrelevant. It remains polynomial, thus in P. In other words, because the original element is in P, you can take every poly-time transformation for free (not resulting in a higer complexity class). $\endgroup$ Apr 8, 2015 at 15:38 -
2$\begingroup$ Knapsack as an optimization problem is certainly not NP-complete, because it's not a decision problem, so not in NP. In any case, I understand what you are saying, but this is the kind of undergrad-level details that I think should be taken for granted on a research level forum like CStheory@SE, just as I don't expect to see an explanation about how convergence in probability is not the same as almost sure convergence on Mathoverflow. $\endgroup$ Apr 8, 2015 at 18:49