4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ This related question may interest you. $\endgroup$ – Raphael Oct 1 '14 at 20:19
  • $\begingroup$ Sure, for example finding maximum likelihood estimate for a Gaussian mixture is NP-Hard. $\endgroup$ – Nicholas Mancuso Oct 1 '14 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 Oct 2 '14 at 2:35
2
$\begingroup$

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.

$\endgroup$

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.