While there are many known NP-complete problems, they all seem to be discrete in the solution space. What is the underlying principle for this?

  • $\begingroup$ the questions are closely related but not exactly the same. note that complexity of real arithmetic is/ can be a complicated topic. the accuracy/ bounds come into play. an example where this shows up in a very complex way is in gaussian elimination (over rationals). its in P but it requires very delicate analysis of the "size" (roughly, number of digits) of the rationals involved. there are some deep refs on that one. a lot of this seems to have to do with CS originating more as the study/ aspects of discrete math than continuous. $\endgroup$ – vzn Apr 24 '15 at 5:40
  • $\begingroup$ You can have discrete problems with very large search spaces that are still polynomial time solvable. $\endgroup$ – Juho Apr 24 '15 at 10:47

It could appear to be the case that "discrete problems" are hard while "continuous problems" are easy. In fact, the exact question has already been asked on TCS.SE here. The answers list some continuous problems that area actually hard to solve.

As usual, computational problems come in all colors, shapes, and sizes. It is not a rule that continuous problems are always easy. In this sense, there is no "underlying principle". I think the following comment by Sasho Nikolov puts it well:

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.