Complexity Theory for Simpletons
in [Theory]
|
Prev: HEAP SORT
Next: Greedy Algorithm
From: Woeginger Gerhard on 27 Mar 2006 11:06 Craig Feinstein <cafeinst(a)msn.com> wrote: # Gerhard, all you have to do is look at the context of my arguments and # figure out what I mean by "best algorithm". I have all the confidence # in the world that you can do this. No, I definitely cannot find any definition of the term "best algorithm" in your paper, and no, I am not able to guess its intended meaning from the context. There is no mention of your model of computation. Are you using 1-tape turing machines? Multi-tape Turing machines? The RAM model? C-programs? How do you count the number of elementary steps used by such a "best algorithm"? I strongly suspect that you are deriving mathematical properties for an object that does not exist. --Gerhard ___________________________________________________________ Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/
From: tchow on 27 Mar 2006 11:08 In article <1143471651.045706.148750(a)z34g2000cwc.googlegroups.com>, Craig Feinstein <cafeinst(a)msn.com> wrote: >I welcome anyone to read my paper and decide for yourself whether you >agree or not. The arguments in my paper stand on their own. Just out of curiosity, has anyone actually read your arguments and agreed with you? If not, that would give an interesting interpretation of "The arguments in my paper stand on their own." :-) -- Tim Chow tchow-at-alum-dot-mit-dot-edu The range of our projectiles---even ... the artillery---however great, will never exceed four of those miles of which as many thousand separate us from the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
From: Woeginger Gerhard on 27 Mar 2006 11:33 Craig Feinstein <cafeinst(a)msn.com> wrote: # Gerhard, all you have to do is look at the context of my arguments and # figure out what I mean by "best algorithm". I have all the confidence # in the world that you can do this. But this really is a crucial point. In the Turing machine model of computation, there is no such thing as a "fastest algorithm" or a "best algorithm". There is the linear speedup theorem http://en.wikipedia.org/wiki/Linear_speedup_theorem that says that for every real c with 0<c<1 and for every Turing machine with time complexity f(n), there is another Turing machine that solves the same problem in time c*f(n). ================================== Hence, in the Turing machine model, there is no such thing as a "best algorithm" for solving the SUBSET-SUM problem. In your paper, you do not discuss your underlying model of computation. If we put your arguments into the context of the Turing machine model, then your argument essentially boils down to the following. 1. I assume that there exists a fastest algorithm A for SUBSET-SUM. (Comment: The linear speedup theorem tells us that A does not exist). 2. I prove that A has exponential running time. (Comment: That's clearly true. Non-existing objects have all kinds of mathematical properties.) 3. I conclude that every algorithm B for SUBSET-SUM has exponential running time. (Comment: This argument is **WRONG**. You cannot compare the running time of an existing algorithm B against the running-time of a non-existing algorithm A). ================================== Hence, your arguments all fail horribly in the Turing machine model of computation. There might be other models of computation, where your arguments do work out. But you have to tell us, which model you had in mind. And you have to prove that in your model of computation there indeed exists something like a "best algorithm". --Gerhard ___________________________________________________________ Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/
From: Ben Pfaff on 27 Mar 2006 11:33 "Craig Feinstein" <cafeinst(a)msn.com> writes: > I welcome anyone to read my paper and decide for yourself whether you > agree or not. The arguments in my paper stand on their own. Has your paper been accepted to any peer-reviewed conferences or journals? -- Ben Pfaff email: blp(a)cs.stanford.edu web: http://benpfaff.org
From: Craig Feinstein on 27 Mar 2006 11:56
Roughly, I mean that algorithm A is "the best algorithm for solving subset-sum with respect to n on computer X" if the worst-case running-time of A for all subsets of size n on computer X is better than that of any other algorithm running on subsets of size n on computer X. You can also look at my paper that I refer to in the bibliography, "Evidence that P != NP" for how I treat the fact that it is possible for numbers in a finite set of size n to be arbitrarily large and therefore the worst-case running-time could conceivably be infinity with respect to fixed n. This is really not a problem; it just requires a little technical fix. Craig |