Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
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 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 at 19:37
    
also similar to curse of dimensionality... –  vzn Jan 2 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 at 6:59
1  
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 at 18:45
add comment

2 Answers

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.

share|improve this answer
2  
Arguably, "rapid" means at least exponential in many contexts. –  Raphael Jan 3 at 6:41
add comment

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.

share|improve this answer
    
So what is the formal term of it? –  TheNotMe Jan 2 at 19:05
1  
Not that I know of any direct formal correspondent, but terms like "intractability" and "exponential growth" seem like good alternatives. –  tbirdal Jan 2 at 22:01
1  
@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 at 0:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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