Is it a rule that discrete problems are NP-hard and continuous problems are not?

Question

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?

Answer 1

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.

Answer 2

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).

Answer 3

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.

Answer 4

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.

Answer 5

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