See also: Traveling Salesman Problem, Brute Force
What's the best way of dealing with a Combinatorial Explosion? Well, I could tell you, but it would result in a Combinatorial Explosion. This is to say there are many problems which, while computable, have complexities which increase so fast there's no way to add enough hardware to make their results accessible before the death of the universe. The time required is Really Big Numbers. Combinatorial Explosion may be Nature's way of telling you you're asking the wrong question.
[Shouldn't this be spelled "Combinator ic Explosion"? www.google.com 
lists 500 hits for 'ic', and 5,000 for 'ial', but blame could lie in the pernicious influence of automated spelling checkers...]
In English There Is More Than One Way To Do It...
Or you may have the right question but the wrong answer. I work in electronic CAD, and many of the problems we have to deal with are Np Complete or worse. But we're usually saved because the particular instance of the problem comes from a design that a person did. Because people can't design large things without structure, the instance has a lot of structure in it. Then you just need to find appropriate heuristics to exploit that structure. The methods may indeed take longer than the lifetime of the universe on a random (unstructured) instance, but we don't care. Designing suitable heuristics is why they pay us...
Or perhaps you don't need the right answer; you only need a Good Enough answer. You don't need the optimal solution to a 10000-node Traveling Salesman Problem; you can get by with an answer within 20% of optimal. You don't need the smallest element in a lattice; you can use the LLL algorithm to obtain an element at most twice as large.
Furthermore, even when an algorithm is not guaranteed to work in polynomial time, when applied to typical problems it often works faster than mathematically expected. The simplex algorithm is not guaranteed to solve a Linear Programming problem in polynomial time. One can create a problem where the algorithm visits every vertex of the allowable polyhedron, but this tends never to occur in practice. --Eric Jablow
Mathematicians like a precise definition of 'Good Enough'. Engineers can typically do without. I once had a teacher who told me: After you've learned your problem is in NP or Np Complete? That's when things get interesting.
See original on c2.com