Contrary to semi-educated belief, NP-complete problems are not necessarily intractable. Often such problems are intractable, but not always. If a problem is NP-complete, this means that there is no polynomial-time algorithm for solving the problem
- for the worst case,
- as the problem size grows,
- finding exact solutions,
- with certainty,
- as far as anyone knows.
One way out of this (#5) is to show how to solve NP-complete problems efficiently. That may not be possible, and it hasn’t been possible so far, so we’ll not worry about this one. But that still leaves four options:
- special cases
- small problem sizes
- approximate solutions
- probabilistic solutions.
For example, the Traveling Salesman problem is NP-complete. But it’s easy to find solutions for a small number of cities by brute force. And even for a moderate number of cities, people routinely find solutions; there’s even an iPhone app for finding solutions. For larger problems, there are algorithms that yield near-optimal solutions with high probability.
Similar remarks hold for other kinds of problems deemed intractable. For example, some say you can’t find the roots of a 5th degree polynomial. Isn’t that a theorem? No. There’s a theorem that says you cannot find
- exact solutions,
- in general,
- using a finite sequence of certain mathematical operations.
So there are three loop holes here:
- approximate solutions,
- special cases, and
- more general operations.
If you only want to find solutions to 100 decimal places, for example, that’s doable.
Most integrals cannot be computed
- by a typical calculus student,
- with certainty,
- in terms of elementary functions.
But often integrals can be computed by some combination of
- more sophisticated exact techniques,
- numerical approximation,
- randomized algorithms, and
- a broader class of functions.
For example, some say that the integral of exp(-x2) cannot be computed. Of course it can, though there is not a finite combination of elementary functions that gives the exact integral. You can compute the integral exactly in terms of the error function erf(x), or compute it numerically to any desired accuracy. You could even approximate the integral with a Monte Carlo method, though there’s no point in using that approach here. For many high-dimensional integration problems, some sort of Monte Carlo is the only practical approach.
Maybe you need to solve a problem for which none of the loop holes given here apply. That’s often the case. I’m not saying that there’s always a way out, only that sometimes there is. Sometimes problems thought to be intractable are not.