Loading ...
Sorry, an error occurred while loading the content.
 

Re: Combinatorial Explosion

Expand Messages
  • Jim Bromer
    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
    Message 1 of 44 , May 1, 2005
      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
      something.

      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.

      Jim Bromer
    • Jim Bromer
      ... be 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. ... I
      Message 44 of 44 , May 10, 2005
        --- In ai-philosophy@yahoogroups.com, "John J. Gagne"
        <fitness4eb@c...> wrote:
        > I think Jim Bromer suggested that the combinatorial explosion could
        be 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. Gagne

        I 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-
        control reaction.

        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
        inversely intractable.)

        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
        subject.

        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
        working on.

        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.

        Jim Bromer
      Your message has been successfully submitted and would be delivered to recipients shortly.