4
$\begingroup$

Just looking for a simple example of why Differential Equations can be NP hard

Edit:

It appears that the answer below may be what I was looking for, but I am clarifying just in case:

Slides 58--72 here show a SAT reduction.

Background:

I remember reading somewhere that improving the approximated solutions to NP hard problems would lead to better approximate numeric solutions. (e.g. weather predictions via Differential Equations)

Is this true? and if so, then in a very general sense, I am trying to understand where the "NP hardness" arises in solving Differential Equations and other numeric problem solving algorithms, if at all.

here is a related link although it does not mention Differential Equations directly

$\endgroup$
5
  • $\begingroup$ Please give some background. $\endgroup$ Feb 19, 2014 at 19:43
  • 1
    $\begingroup$ Give a specific decision problem, not just something as vague as "solving differential equations", and ask on cstheory.stackexchange.com please. $\endgroup$ Feb 19, 2014 at 19:56
  • $\begingroup$ I think it's well-established precedent that questions on complexity theory are on-topic for Math Overflow, irrespective of the existence of cstheory. $\endgroup$
    – arsmath
    Feb 19, 2014 at 22:44
  • 1
    $\begingroup$ Generic differential equations cannot be "solved" in any reasonable meaning of the word. So it is unclear what you are asking. $\endgroup$ Feb 20, 2014 at 1:01
  • $\begingroup$ I've given some background plus a link $\endgroup$ Feb 21, 2014 at 1:03

1 Answer 1

3
$\begingroup$

Slides 58--72 here show a SAT reduction.

$\endgroup$

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