Re: Combinatorial Explosion
- My mathematics is not good enough to continue spending a lot of time on
the Traveling Salesman Problem and the P=?NP question, but I am going
to continue working on my own combinatoric theorems because I did see
I understand that even if someone came up with a minimal solution to
the Traveling Salesman Problem there would not be a good way to prove
that it really was The Minimal Solution.
- --- In firstname.lastname@example.org, "John J. Gagne"
> I think Jim Bromer suggested that the combinatorial explosion couldbe used as a solution rather than a problem. This was just an
implied suggestion on his part and I'm not even sure if that was
what he meant or not.
> John J. GagneI was suggesting that the combinatorial explosion could be used as a
solution rather than a problem, although I rephrased my suggestion
after Pei mentioned that the term explosion suggested an out-of-
We can use the combinatorial potential, both in our lives and in our
projects, to explore new ideas. The combinatorial explosion is a
problem that affects many aspects of artificial intelligence. People
often feel that if it weren't for the CE Problem, they could discover
optimal solutions to many problems relative to the quality of the
information they have acquired concerning the problem. However I am
saying that we should not give up just because the combinatorial
problem is too difficult; instead we can take the combinatorial
potential and use it as leverage to explore some of the various
possibilities that do exist.
JJG understood what I meant when he went on to say,
"Certainly, within any sufficiently large combinatorial problem there
is a large number of solutions which are nearly ideal and an even
larger number which are only slightly less than nearly ideal etc,
etc. If we view the problem from this perspective then it does seem
to be much more of a solution than a problem. A combinatorial
explosion of solutions."
If there are a large number of potential solutions to a problem
relative to an appropriate evaluation of difficulty then the
combinatorial potential might be used to effectively help in finding
a good working solution. (Other constraints are also necessary. The
ratio of solutions to non-solutions cannot be infinitesimal or
There are also cases where there may be many different paths towards
a solution. In these cases, the discovery of a new relationship that
might seem to be on the periphery of our immediate focus may later
turn out to be helpful in gaining significant insight about the
And since we are interested in a wide range of different subjects,
our goals may be shifted toward problems that we are more equipped to
deal with when some new principle comes to light. Since we tend to
use ideas that we are more skilled with when we explore subjects that
are puzzling us at the moment, the exploration of these less familiar
subjects may lead to further insights about the subjects that we use
more capably. In these cases the combinatorial potential may lead
toward a new understanding of those topics that most interest us even
if we cannot use them to solve the particular puzzle that we were
I also realized that combinatorial problems were related to problems
of optimization, sorting and searching.
While my original statements were not in reference to any
mathematical problems, this insight could be expressed in the form of
a mathematical conjecture.