A combinatorial explosion refers to an exponential or polynomial increase in complexity depending on the number of input variables and the states of those input variables.
The first simple example is imagine we have n variables with Z possible
states for each variable.
The number of possible resulting combinations of states is Z^n.
So consider 3 booleans. The resulting combinations is 2^3.
A boolean combinatorial explosion is exponential, as the number of states is
fixed to 2. But the number of booleans is unknown. Here the exponent is what
matters. An order of magnitude increase in number of states per variable will
result in less complexity than an order of magnitude increase in the number of
variables.
-- in general, an increase in the number of states will result in less
-- complexity than an increase in the variables
20^3 < 2^30
These types of problems can be visualised as decision trees.
Another example is the number of lines of communication between nodes in a graph.
As the nodes increase, the lines increase by:
n(n-1)
------
2
This is actually polynomial complexity: n^2 - 0.5n + 0.
Also expressed as binomial coefficient:
n
( )
2
Note that in general any exponential time algorithm will always use more resources that any polynomial algorithm. If our boolean example was an algorithm, it would be exponential, as the number of booleans increase, they result in an increase in the exponent.
Meaning from the n set, how many 2 combinations can I select. So for a 3 node
graph {1, 2, 3}, that is 1-1, 1-2, 2-3.
It's a slightly different problem. There isn't an increase in the number of variables nor states of variables. The nodes aren't variable, they don't change in any way. They fixed in the way they behave.
Therefore it doesn't seem to make sense to call this problem a combinatorial explosion of complexity. It would make more sense if we were trying to find how many kinds of graphs can there be with additional nodes added. In this current problem, there is only one configuration of a graph, every time a node is added.
Consider if the graph's nodes could have 10 different states. Then there's a combinatorial explosion in the types of graphs that could result if you add an extra node.