When I read computational complexity I encounter problems like 3-SAT, set cover, knapsack. In the first two variables are discrete. In knapsack the weights and values are integer and all three problems have a combinatorial structure, what I mean is selecting a finite number from a finite set.
How about problems in continuous domains like finding the minimum or maximum of a function in real numbers? Or solving a differential equation to find a function? Can we prove that these problems too are hard or easy in a computational complexity sense?
Finally how do I know, by looking at a problem, if asking "is the problem NP-hard?" is a valid question?
-
$\begingroup$ This related question may interest you. $\endgroup$Raphael– Raphael2014年10月01日 20:19:50 +00:00Commented Oct 1, 2014 at 20:19
-
$\begingroup$ Sure, for example finding maximum likelihood estimate for a Gaussian mixture is NP-Hard. $\endgroup$Nicholas Mancuso– Nicholas Mancuso2014年10月01日 21:23:36 +00:00Commented Oct 1, 2014 at 21:23
-
$\begingroup$ Thanks, I believe in your example there is a combinatorial structure such as minimize distance between set of points. $\endgroup$seek– seek2014年10月02日 02:35:07 +00:00Commented Oct 2, 2014 at 2:35
1 Answer 1
I can answer for the first part.
Computational completely is usually defined using Turing machines, that operate over finite alphabets, so questions about algorithms over the reals cannot be answered in that framework.
With regards to possible approaches to machines over the reals, they can be broadly divided into machines that work over representation and machines that can directly and atomically manipulate real numbers.
See also this question here on SE.