5
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ 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$) $\endgroup$
    – Steven Stadnicki
    Commented Jan 2, 2014 at 18:57
  • $\begingroup$ 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. $\endgroup$
    – vzn
    Commented Jan 2, 2014 at 19:37
  • $\begingroup$ also similar to curse of dimensionality... $\endgroup$
    – vzn
    Commented Jan 2, 2014 at 22:17
  • $\begingroup$ 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. $\endgroup$
    – seteropere
    Commented Jan 3, 2014 at 6:59
  • 1
    $\begingroup$ 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... $\endgroup$
    – vzn
    Commented Jan 3, 2014 at 18:45

2 Answers 2

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ Arguably, "rapid" means at least exponential in many contexts. $\endgroup$
    – Raphael
    Commented Jan 3, 2014 at 6:41
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ So what is the formal term of it? $\endgroup$
    – TheNotMe
    Commented Jan 2, 2014 at 19:05
  • 1
    $\begingroup$ Not that I know of any direct formal correspondent, but terms like "intractability" and "exponential growth" seem like good alternatives. $\endgroup$
    – Tolga Birdal
    Commented Jan 2, 2014 at 22:01
  • 1
    $\begingroup$ @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. $\endgroup$
    – David Richerby
    Commented Jan 3, 2014 at 0:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.