Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!husc6!yale!Krulwich-Bruce
From: Krulwich-Bruce@cs.yale.edu (Bruce Krulwich)
Newsgroups: comp.ai.neural-nets
Subject: Re: implementation of "traveling salesman algorithm" on connection machine
Keywords: TSP, connection machine
Message-ID: <49733@yale-celray.yale.UUCP>
Date: 5 Feb 89 18:18:52 GMT
References: <1637@cps3xx.UUCP> <49632@yale-celray.yale.UUCP>
Sender: root@yale.UUCP
Reply-To: Krulwich-Bruce@cs.yale.edu (Bruce Krulwich)
Distribution: usa
Organization: Computer Science, Yale University, New Haven, CT 06520-2158
Lines: 14
In-reply-to: root@yale.UUCP (Celray Stalk)

>>   Does anyone know about any implementation of efficient
>>algorithms for the Traveling salesman Problem (TSP) on the
>>Connection Machine ?
>
>Anyone who answers that question "Yes" is not telling the truth. The
>TSP is known to take at least exponential time, CM or no CM. 

Is that true if there are O(2^n) processors available for solving an n-city
TSP??  This may very well be the case if using a CM.

Bruce Krulwich