In the theory of NP-completeness, researchers refer to the concept of combinator
ID: 654879 • Letter: I
Question
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?
Explanation / Answer
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.