Complexity Theory for Simpletons
in [Theory]
|
Prev: HEAP SORT
Next: Greedy Algorithm
From: Bryan Olson on 27 Mar 2006 06:31 Craig Feinstein wrote: > Tim, I appreciate that you have read my paper and have given your > feedback. I don't agree with your criticisms, but I don't really have > the time to argue with you either, so let's just agree to disagree. Friendly as disagreement may be, there's no question that the argument for "Theorem 2" in http://arxiv.org/abs/math/0312309 just doesn't work. As Tim Chow noted, "Proofs [...] can derive general facts about sequences of high complexity without ever giving a single such sequence explicitly." Similarly, your P != NP proof has the most common error: the unjustified assumption that things have to be done a certain way. No, the best algorithm doesn't necessarily have to attack your two sub-problems. -- --Bryan
From: Googmeister on 27 Mar 2006 07:14 Craig Feinstein wrote: > Tim, I appreciate that you have read my paper and have given your > feedback. I don't agree with your criticisms, but I don't really have > the time to argue with you either, so let's just agree to disagree. Tim's has exposed a serious flaw in your argument. Since the flaw is so fundamental, if you don't have time to reconcile it, I think you should retract your paper before others spend their time reading it. Thanks again to Tim for his willingness to carefully read your work and clearly articulate its faulty reasoning (when it's hard for those more cynical to not wonder whether this is just a trolling expedition.)
From: Craig Feinstein on 27 Mar 2006 10:00 I'm sorry, but Tim hasn't exposed any flaw whatsoever. Tim simply doesn't want to believe my arguments, so he doesn't believe them and makes up a few reasons to justify his belief. The same thing with Bryan Olson's comments. Their arguments are so transparent that it's not worth it for me to waste my time debunking them. Whatever I say, they will simply make up another reason why I'm "wrong". 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. Craig
From: Woeginger Gerhard on 27 Mar 2006 10:24 Googmeister <googmeister(a)gmail.com> wrote: # # Craig Feinstein wrote: #> Tim, I appreciate that you have read my paper and have given your #> feedback. I don't agree with your criticisms, but I don't really have #> the time to argue with you either, so let's just agree to disagree. # # Tim's has exposed a serious flaw in your argument. Since the # flaw is so fundamental, if you don't have time to reconcile it, # I think you should retract your paper before others spend their # time reading it. # # Thanks again to Tim for his willingness to carefully read your # work and clearly articulate its faulty reasoning (when it's hard # for those more cynical to not wonder whether this is just a # trolling expedition.) Here is another faulty point in the reasoning of this paper: The paper tries to prove by induction on n that the best algorithm for solving the SUBSET-SUM problem on sets with n integers is the so-called Meet-in-the-Middle algorithm. Fault: The notion of "best algorithm" is not defined. What does it mean? Possibility #1: A "best algorithm" is an algorithm that makes the smallest possible number of steps for one particular value of n. If this is the intended meaning: How do you define "smallest possible number of steps"? What is your model of computation? Possibility #2: A "best algorithm" is an algorithm that makes the smallest possible number of steps for all possible values of n? If this is the intended meaning: How do you define "smallest possible number of steps"? What is your model of computation? ====================== The notion of "best algorithm" is unclear, and we do not even know whether such a mathematical object exists. The paper argues: If: the mathematical object exists, then: its running time must be exponential However, if this object does not exist (which is probably the case), then this statement is empty. There might be other algorithms, that are not "best algorithms", but that have polynomial running time. --Gerhard ___________________________________________________________ Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/
From: Craig Feinstein on 27 Mar 2006 10:56
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. Craig |