Author: Dann Corbit
Date: 10:26:17 05/09/01
Go up one level in this thread
On May 09, 2001 at 13:08:18, Ricardo Gibert wrote: [snip] >In the traveling salesman problem, f(n) is NP rather than P, since there does >*not* exist a constant c sth f(n) = c*P, since n is unbounded. > >It essential to understand the terms bounded, unbounded and infinity in their >proper context. Since there are a finite number of cities, the travelling salesman problem has SUDDENLY BECOME BOUNDED and you have solved question as to whether a polynomial time solution exists. In fact, by your definition, you have found a solution which is O(1). I imagine the computer science community will be very happy to hear about this. They don't have a nobel prize for computer science, which is probably just as well.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.