What is combinatorial explosion?

In the theory of NP-completeness, researchers refer to the concept of combinatorial explosion. Some researchers use it as justification for intractability or NP-completeness. Others use it to refer to the exponential growth of possible solutions of an intractable problem while others use to refer to the apparent exponential time required to solve NP-complete problems. I am interested in formal connection to combinatorics.


Is there combinatorial basis that captures and explains the phenomena of combinatorial explosion?

Assume your algorithm has a complexity of $\Theta(n!)$. For small $n$ your problem can be easily solved in any machine, however when $n$ grows large enough even the fastest computers cannot figure out the solution. As the options and cases to observe increase, your complexity increases so rapidly that even for some reasonable $n$, it becomes impossible to run the algorithm with current resources. This is combinatorial explosion.

It is however, as mentioned, an informal term.

StackExchange Computer Science Q#19459, answer score: 3