# 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$) – Steven Stadnicki Jan 2 '14 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 '14 at 19:37
also similar to curse of dimensionality... – vzn Jan 2 '14 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. – seteropere Jan 3 '14 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 '14 at 18:45

There is no formal connection to anything because "combinatorial explosion" is an informal term. It refers to rapid growth of a function caused by the combinatorics of the situation.

-
Arguably, "rapid" means at least exponential in many contexts. – Raphael Jan 3 '14 at 6:41

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.

-
So what is the formal term of it? – TheNotMe Jan 2 '14 at 19:05
Not that I know of any direct formal correspondent, but terms like "intractability" and "exponential growth" seem like good alternatives. – Tolga Birdal Jan 2 '14 at 22:01
@TheNotMe There is no formal term. When we say that it's an informal term, we don't mean that it's slang or something like that; we mean that it has no precise definition and, therefore, doesn't correspond to anything formal. – David Richerby Jan 3 '14 at 0:47