Combinatorial Explosion

What's the best way of dealing with a CombinatorialExplosion? Well, I could tell you, but it would result in a CombinatorialExplosion. 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 ReallyBigNumbers. CombinatorialExplosion may be Nature's way of telling you you're asking the wrong question.

[Shouldn't this be spelled "Combinator ic Explosion"? http://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 ThereIsMoreThanOneWayToDoIt...

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 NpComplete 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 GoodEnough answer. You don't need the optimal solution to a 10000-node TravelingSalesmanProblem; 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 LinearProgramming 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. --EricJablow

Mathematicians like a precise definition of 'GoodEnough'. Engineers can typically do without. I once had a teacher who told me: After you've learned your problem is in NP or NpComplete? That's when things get interesting.

CategoryJargon, CategoryComplexity