<p>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 <a href="https://en.wikipedia.org/wiki/Existential_theory_of_the_reals">existential theory of the reals</a>, 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.</p>

<p>There are other continuous problems that are even harder: for instance, finding a shortest path among polyhedral obstacles in 3d is PSPACE-complete (Canny &amp; Reif, FOCS'87).</p>

CC BY-SA 3.0
2015-04-12T22:31:24.513Z
'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.
Steven Stadnicki
CC BY-SA 3.0
2015-04-07T22:42:25.197Z
2015-04-07T22:42:25.197Z
David Eppstein
<p>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.</p>

<p>The problem is the <em>Sum of Square Roots</em> 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 <em>be</em> 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 &mdash; a set of integers and a yes/no question about them &mdash; 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.</p>

CC BY-SA 3.0
2015-04-13T00:26:18.923Z
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 (http://cstheory.stackexchange.com/a/4010/8985)
Joe Bebel
CC BY-SA 3.0
2015-04-15T17:09:02.247Z
@JoeBebel Very good point - I've revised my language slightly to reflect that.  Thank you!
Steven Stadnicki
CC BY-SA 3.0
2015-04-12T22:43:41.817Z
2015-04-15T17:08:32.757Z
2015-04-15T17:08:32.757Z
Steven Stadnicki
<p>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
<a href="http://web.mit.edu/~a_a_a/Public/Publications/convexity_nphard.pdf">deciding convexity of quartics (degree-4 polynomials) is NP-hard</a>.</p>

<p>Which means even if you already have the optimum somehow, simply <em>proving</em> that you are at the optimum is already NP-hard.</p>

CC BY-SA 3.0
2015-04-08T18:35:36.147Z
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.
willeM_ Van Onsem
CC BY-SA 3.0
2015-04-08T18:36:59.070Z
@CommuSoft: Not really... the discreteness isn't the issue. Check out the [shortest path problem](https://en.wikipedia.org/wiki/Shortest_path_problem#Linear_programming_formulation), 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).
user541686
CC BY-SA 3.0
2015-04-08T18:39:14.563Z
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.
willeM_ Van Onsem
CC BY-SA 3.0
2015-04-08T18:39:48.270Z
@CommuSoft: Did you read the comment fully? I'm not talking about ILP.
user541686
CC BY-SA 3.0
2015-04-08T18:42:22.237Z
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.
willeM_ Van Onsem
CC BY-SA 3.0
2015-04-08T18:47:28.603Z
@CommuSoft: Then you seem to be saying exactly what I'm saying, i.e. it's because of the constraints, not merely because of the discreteness.
user541686
CC BY-SA 3.0
2015-04-08T18:49:47.957Z
No you say: "*but it's not the discreteness itself that's the problem...*", I would say "*The problem is mainly the discreteness, only in rare occasions, if the constraints are well structured, the problem is easy solvable*". The same goes for *quadratic programming*, you can easily transform a linear programming problem in a quadratic one, and evidently, you can solve such problem still in poly time. But that's only because you have constraint your problem enough.
willeM_ Van Onsem
CC BY-SA 3.0
2015-04-08T18:54:17.123Z
@CommuSoft: Sorry but I think what I said is on the mark so I don't think I'll be editing it...
user541686
CC BY-SA 3.0
2015-04-08T09:58:22.020Z
2015-04-08T09:58:22.020Z
user541686
<p>Although for <em>some</em> popular problems, it is indeed true, I think both assumptions are - depending on what you define as an optimization problem - not true.</p>

<p>First some definitions: most optimization problems are <strong>not part of NP</strong>. For instance for the <em>Knapsack problem</em>: one cannot exploit non-determinism to construct the most valuable bag, simple because the different non-deterministic branches have no shared memory. <strong>NP</strong> is also defined as "polynomially verifiable" (verifying a certificate) <code>[1, p. 34]</code>. In this case the certificate is for instance a <em>bag</em>: a bitstring where if the <em>i</em>-th bit is set, it implies the <em>i</em>-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 <em>decision variant</em>), 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 <strong>NP</strong> and <strong>EXP</strong>: in <strong>EXP</strong>, you can enumerate over all possible bags and do bookkeeping about which bag is the best one.</p>

<p>The <strong>decision variant</strong> of the optimization problems is in some cases part of <strong>NP</strong>, one needs to make a clear distinction between the <em>maximization flavor</em> and the <em>decision flavor</em>. In the decision flavor, the question is: "<em>Given an optimization problem, and a utility bound, is there a solution with a utility greater than or equal to that bound</em>" (or slightly modified for a minimization problem).</p>

<p>I also assume that by <strong>NP</strong> you mean the (hypothetical) part of <strong>NP</strong> that is not part of <strong>P</strong>. If <strong>P=NP</strong>, of course <strong>NP-complete</strong> still exists, but it will be equal to <strong>P</strong> (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 "<em>gap</em>" you are stating in your question).</p>

<blockquote>
  <p>I increasingly notice that most discrete problems are NP-complete.</p>
</blockquote>

<p>Now that we have sorted that out: there are a lot of optimization problems that are in <strong>P</strong>: <em>shortest path problem</em>, <em>maximum flow problem</em> (for integral capacities), <em>minimum spanning tree</em> and <em>maximum matching</em>. 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 <strong>P</strong> is not equal to <strong>NP</strong>, these problems thus can't be <strong>NP-complete</strong>.</p>

<p>One can furthermore walk through the <a href="http://en.wikipedia.org/wiki/Polynomial_hierarchy" rel="nofollow"><em>polynomial hierarchy</em></a>, 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).</p>

<blockquote>
  <p>Whereas optimizing continuous problems is almost always easily achievable.</p>
</blockquote>

<p>A popular continuous problem that is <strong>NP-hard</strong> is <a href="http://en.wikipedia.org/wiki/Quadratic_programming#Complexity" rel="nofollow"><em>quadratic programming</em></a>.</p>

<p>In quadratic programming, one is looking for a vector $\vec{x}$ such that:</p>

<p>$$\dfrac{\vec{x}^T\cdot Q\cdot\vec{x}}{2}+\vec{c}^T\cdot\vec{x}$$ is minimized satisfying:</p>

<p>$$A\cdot\vec{x}\leq\vec{b}$$</p>

<p>Actually <em>Linear programming</em> has long been considered <strong>NP-hard</strong> as well, but with very well performing <em>heuristics</em> (the <em>Simplex</em> method). <em><a href="http://en.wikipedia.org/wiki/Karmarkar%27s_algorithm" rel="nofollow">Karmarkar's algorithm</a></em> is however in <strong>P</strong>.</p>

<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.</p>

<p><strong>Bibliography</strong></p>

<p><code>[1]</code> <a href="https://www.cs.duke.edu/~reif/courses/complectures/books/AB/ABbook.pdf" rel="nofollow"><em>Computational Complexity, a modern approach</em>, <em>Sanjeev Arora and Boaz Barak</em></a></p>

CC BY-SA 3.0
2015-04-08T07:47:11.537Z
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).
Sasho Nikolov
CC BY-SA 3.0
2015-04-08T07:50:39.457Z
@AndrásSalamon: point taken. I removed that part. It was indeed a bit sloppy.
willeM_ Van Onsem
CC BY-SA 3.0
2015-04-08T15:29:26.457Z
@AndrásSalamon: evidently that's true. Therefore it says: "*Given P is not equal to NP, these problems thus can't be NP-complete.*"
willeM_ Van Onsem
CC BY-SA 3.0
2015-04-08T15:38:36.030Z
@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).
willeM_ Van Onsem
CC BY-SA 3.0
2015-04-08T18:27:03.980Z
The following is not clear to me: "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." Maybe you mean that giving an upper bound on the value of the optimal packing is coNP-complete so not likely to be in NP? In any case, my subjective opinion is that the precise distinctions between optimization, search, and decision problems are really beside the point here.
Sasho Nikolov
CC BY-SA 3.0
2015-04-08T18:32:04.277Z
@SashoNikolov: they are not: the *decision flavor* of the *knapsack problem* is clearly NP-complete, the *optimization flavor* is almost certainly not. NP is not equal to EXP: NP means you *can verify a certificate in polynomial time*. That certificate is for instance a bitstring that specifies per item whether it is part of the bag. Now you can easily verify that a certain bag is more valuable than a given value, but you cannot - as far as we know - given a bag decide if that bag is the most valuable of all bags.
willeM_ Van Onsem
CC BY-SA 3.0
2015-04-08T18:49:27.600Z
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.
Sasho Nikolov
CC BY-SA 3.0
2015-04-08T18:52:28.293Z
@SashoNikolov: given the sloppyness of the original title of this question, I think such problems must be addressed in answers. I sometimes answer students that have read in a book *the decision variant of the knapsack problem is NP-complete*, they immediately generalize it to *the entire knapsack problem is NP-complete.*. And providing some additional details is in general not a problem.
willeM_ Van Onsem
CC BY-SA 3.0
2015-04-07T23:29:27.400Z
2015-04-09T17:25:58.390Z
2015-04-09T17:25:58.390Z
willeM_ Van Onsem
<p>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$$</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2015-04-08T01:31:27.210Z
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.
Joe Bebel
CC BY-SA 3.0
2015-04-08T19:28:26.470Z
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.
E.P.
CC BY-SA 3.0
2015-04-08T21:10:48.247Z
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.
Joe Bebel
CC BY-SA 3.0
2015-04-12T06:15:47.957Z
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.
Joe Bebel
CC BY-SA 3.0
2015-04-07T21:49:37.327Z
2015-04-07T21:49:37.327Z
Joe Bebel
<p>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?</p>

CC BY-SA 3.0
2015-04-07T20:44:48.470Z
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.
Sasho Nikolov
CC BY-SA 3.0
2015-04-07T21:52:51.797Z
Here is a simple continuous optimisation problem that is NP-hard to solve: http://cstheory.stackexchange.com/questions/14630/exact-algorithms-for-non-convex-quadratic-programming
Jukka Suomela
CC BY-SA 3.0
2015-04-08T04:24:39.427Z
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.
Suresh Venkat
CC BY-SA 3.0
2015-04-08T09:53:02.190Z
For those reading the question -- see [Witsenhausen's counterexample](https://en.wikipedia.org/wiki/Witsenhausen%27s_counterexample) for an interesting case. It's not known to be NP-hard, but it's an open problem and its discretization has been shown to be NP-hard.
user541686
CC BY-SA 3.0
2015-04-08T14:40:46.997Z
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.
usul
CC BY-SA 3.0
2015-04-09T00:04:36.547Z
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.
Sasho Nikolov
CC BY-SA 3.0
2015-04-14T21:17:38.010Z
I think @SureshVenkat has most of the point that differentiates the objective of discrete opt vs continuous. Not only local optima, but also that continuous opt usually looks for a rational *approximation* while discrete opt problems are usually exact. Continuous methods are usually measured in terms of convergence rates, or number of steps to get an answer within epsilon. If one of these 'gradient techniques' never terminates (but only gets closer and closer, e.g. newton's method to solve x^2=2) then it would not even be considered an algorithm in the discrete world.
JimN
<cc.complexity-theory><co.combinatorics><optimization>
Is it a rule that discrete problems are NP-hard and continuous problems are not?
alekdimi
# Is it a rule that discrete problems are NP-hard and continuous problems are not?

(Asked by: username_0 on 2015-04-07)

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?

**Tags:** cc.complexity-theory, co.combinatorics, optimization
> **Comments:**
> **username_1**: 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.  
> **username_2**: Here is a simple continuous optimisation problem that is NP-hard to solve: http://cstheory.stackexchange.com/questions/14630/exact-algorithms-for-non-convex-quadratic-programming  
> **username_3**: 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.  
> **username_4**: For those reading the question -- see [Witsenhausen's counterexample](https://en.wikipedia.org/wiki/Witsenhausen%27s_counterexample) for an interesting case. It's not known to be NP-hard, but it's an open problem and its discretization has been shown to be NP-hard.  
> **username_5**: 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.  
> **username_1**: 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.  
> **username_6**: I think @SureshVenkat has most of the point that differentiates the objective of discrete opt vs continuous. Not only local optima, but also that continuous opt usually looks for a rational *approximation* while discrete opt problems are usually exact. Continuous methods are usually measured in terms of convergence rates, or number of steps to get an answer within epsilon. If one of these 'gradient techniques' never terminates (but only gets closer and closer, e.g. newton's method to solve x^2=2) then it would not even be considered an algorithm in the discrete world.  

---

## 5 answers

### Answer by username_9 on 2015-04-07. Score: 43 | Accepted answer

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.

> **Comments:**
> **username_9**: 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.  
> **username_11**: 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.  
> **username_9**: 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.  
> **username_9**: 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.  

---

### Answer by username_7 on 2015-04-07. Score: 26

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](https://en.wikipedia.org/wiki/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).

> **Comments:**
> **username_8**: '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.  

---

### Answer by username_8 on 2015-04-12. Score: 13

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.

> **Comments:**
> **username_9**: 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 (http://cstheory.stackexchange.com/a/4010/8985)  
> **username_8**: @JoeBebel Very good point - I've revised my language slightly to reflect that.  Thank you!  

---

### Answer by username_4 on 2015-04-08. Score: 7

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](http://web.mit.edu/~a_a_a/Public/Publications/convexity_nphard.pdf).

Which means even if you already have the optimum somehow, simply *proving* that you are at the optimum is already NP-hard.

> **Comments:**
> **username_10**: 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.  
> **username_4**: @CommuSoft: Not really... the discreteness isn't the issue. Check out the [shortest path problem](https://en.wikipedia.org/wiki/Shortest_path_problem#Linear_programming_formulation), 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).  
> **username_10**: 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.  
> **username_4**: @CommuSoft: Did you read the comment fully? I'm not talking about ILP.  
> **username_10**: 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.  
> **username_4**: @CommuSoft: Then you seem to be saying exactly what I'm saying, i.e. it's because of the constraints, not merely because of the discreteness.  
> **username_10**: No you say: "*but it's not the discreteness itself that's the problem...*", I would say "*The problem is mainly the discreteness, only in rare occasions, if the constraints are well structured, the problem is easy solvable*". The same goes for *quadratic programming*, you can easily transform a linear programming problem in a quadratic one, and evidently, you can solve such problem still in poly time. But that's only because you have constraint your problem enough.  
> **username_4**: @CommuSoft: Sorry but I think what I said is on the mark so I don't think I'll be editing it...  

---

### Answer by username_10 on 2015-04-07. Score: 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*](http://en.wikipedia.org/wiki/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*](http://en.wikipedia.org/wiki/Quadratic_programming#Complexity).

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](http://en.wikipedia.org/wiki/Karmarkar%27s_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*](https://www.cs.duke.edu/~reif/courses/complectures/books/AB/ABbook.pdf)

> **Comments:**
> **username_1**: 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).  
> **username_10**: @AndrásSalamon: point taken. I removed that part. It was indeed a bit sloppy.  
> **username_10**: @AndrásSalamon: evidently that's true. Therefore it says: "*Given P is not equal to NP, these problems thus can't be NP-complete.*"  
> **username_10**: @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).  
> **username_1**: The following is not clear to me: "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." Maybe you mean that giving an upper bound on the value of the optimal packing is coNP-complete so not likely to be in NP? In any case, my subjective opinion is that the precise distinctions between optimization, search, and decision problems are really beside the point here.  
> **username_10**: @SashoNikolov: they are not: the *decision flavor* of the *knapsack problem* is clearly NP-complete, the *optimization flavor* is almost certainly not. NP is not equal to EXP: NP means you *can verify a certificate in polynomial time*. That certificate is for instance a bitstring that specifies per item whether it is part of the bag. Now you can easily verify that a certain bag is more valuable than a given value, but you cannot - as far as we know - given a bag decide if that bag is the most valuable of all bags.  
> **username_1**: 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.  
> **username_10**: @SashoNikolov: given the sloppyness of the original title of this question, I think such problems must be addressed in answers. I sometimes answer students that have read in a book *the decision variant of the knapsack problem is NP-complete*, they immediately generalize it to *the entire knapsack problem is NP-complete.*. And providing some additional details is in general not a problem.  

---

