Author: Dann Corbit
Date: 10:57:57 05/09/01
Go up one level in this thread
On May 09, 2001 at 13:48:00, Ricardo Gibert wrote: >On May 09, 2001 at 13:26:17, Dann Corbit wrote: > >>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. > >The traveling salesman problem is more than just a practical problem. It is a >theoretical problem too with independent interest. Indeed, but the whole reason we analyze algorithms is to see if we can solve them. If I have an algorithm that is O(f(n)), I know what size of a problem I can attack. If I use the alternative definition that all implementations are O(1), then all my analysis is for nothing. big-O analysis is very much a practical science that deals with problems of manageable size. That is the very core nature of its purpose. If we have inifinite inputs, then nothing is solvable -- (well, maybe O(1)) agreed?
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.