# 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?

• Not rich enough for a proper answer, but I think the key 'combinatorial' piece is the simple fact that $\left|A\otimes B\right|=|A|\cdot|B|$ (and thus $\left|{}\otimes^n{}A\right| = \left|A\right|^n$) Jan 2, 2014 at 18:57
• imho this is nearly the P=?NP problem. there are other contexts for "combinatorial explosion", basically it means "large search space". in that context, it refers to branching possibilities and the apparent reality that solutions can only be found (on average) by lots of branching or also informally "trial and error". it seems to preclude "divide and conquer". agreed its an informal concept but also there are probably multiple ways to formalize the concept.
– vzn
Jan 2, 2014 at 19:37
• also similar to curse of dimensionality...
– vzn
Jan 2, 2014 at 22:17
• I do not know much about complexity but this reminds me of the VC-dimension (VCD) when learning a particular structure. VCD measures the growth rate of a function.. I do not know whether its used in characterising problem complexity or its completely irrelevant. Jan 3, 2014 at 6:59
• yes it reminds me of VC-dimension also. it is one way of characterizing function complexity. also this question seems naturally related to other measures of function complexity eg circuit complexity. yet another is kolmogorov complexity ... so there are many angles on a formal answer...
– vzn
Jan 3, 2014 at 18:45

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.