Talk:Combinatorial explosion (communication)

From Wikipedia, the free encyclopedia

There should be a separate article on Combinatorial Explosion, and its meaning in relation to mathematics, computer science, and any kind of precise analysis. This topic is too general - and too important - to only be treated in relation to cryptography, even if that is the easisest subject on which to say something universally correct. Even if the article ends up delving into psychology and cognitive science, I know from first-hand experience that it would be valuable to many working professionals, regardless of trade.

[edit] OK, a start

I had an essay on this relating to the NHS at http://www.defoam.net/writing/connecting/connect.html so I've used the small diagrams from there.

--Midgley 30 June 2005 19:12 (UTC)

... yes, improved. Midgley 00:11, 15 November 2005 (UTC)

[edit] Exponential in the commonly used sense

"Rapid" doesn't quite convey the shape of the curve (see [1] ) in that it is an increasingly rapid ascent with relatively small increases in the number of nodes connected. Polynomial doesn't fully define it either, in that polynomials don't necessarily increase. Exponential does seem to have a common meaning whcih exactly describes the nature of this effect, whereas I don't have a word which is matehmatically correct for what happens. Anyone? Midgley 14:58, 1 February 2006 (UTC)

In the case described, the increase is merely quadratic: the number of linkages is the series of triangular numbers n*(n+1)/2 (1, 3, 6, 10, 15, etc).

I think this article needs a bit of attention, as that example gives quite a leisurely increase. Combinatorial explosion normally refers to functions where the number of combinations blows up monstrously, typically by a factorial function (see brute-force search and the Travelling salesman problem). 86.139.229.178 19:54, 2 February 2006 (UTC)

Combinatorial pétard?

Don't lose sight of the sort of problem referred to, which is considerable at the accelarating increase as given, please. Midgley 19:57, 2 February 2006 (UTC)