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?

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

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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