Complexity Theory for Simpletons
in [Theory]
|
Prev: HEAP SORT
Next: Greedy Algorithm
From: David Wagner on 27 Mar 2006 16:25 Woeginger Gerhard wrote: >3. I conclude that every algorithm B for SUBSET-SUM has exponential > running time. > (Comment: This argument is **WRONG**. Indeed, not only is the argument wrong, the conclusion is wrong, too. Several of the SUBSET-SUM algorithms mentioned in my prior post have subexponential (but superpolynomial) running time.
From: Craig Feinstein on 27 Mar 2006 17:03 I'm afraid you misunderstood the definition of "better". With respect to the definition of "better" used in my paper, no algorithm has been found that beats Meet-in-the-Middle. If you think I'm lying, then just read Woeginger's 2003 article cited in my paper, the person who posted in this thread. As you can see, 2003 was more recent than 2002, 2000, 1991, so your criticism is invalid - unless of course, you are claiming that Woeginger somehow missed these papers. I'm afraid I don't have time to respond to any more criticisms. Thank you all for your comments. With peace, love, and blessings, Craig
From: David Wagner on 28 Mar 2006 01:59 Craig Feinstein wrote: >I'm afraid you misunderstood the definition of "better". With respect >to the definition of "better" used in my paper, no algorithm has been >found that beats Meet-in-the-Middle. I'm afraid I can't be bothered to read your paper. What is your definition of "better"? >If you think I'm lying, then just >read Woeginger's 2003 article cited in my paper, the person who posted >in this thread. As you can see, 2003 was more recent than 2002, 2000, >1991, so your criticism is invalid - unless of course, you are claiming >that Woeginger somehow missed these papers. I haven't read Woeginger's 2003 article. Sure, it's entirely possible that Woeginger has somehow missed these papers. There are gazillions of papers published each year; it's easy to miss some.
From: Woeginger Gerhard on 28 Mar 2006 06:29 David Wagner <daw(a)taverner.cs.berkeley.edu> wrote: # Craig Feinstein wrote: #>If you think I'm lying, then just #>read Woeginger's 2003 article cited in my paper, the person who posted #>in this thread. As you can see, 2003 was more recent than 2002, 2000, #>1991, so your criticism is invalid - unless of course, you are claiming #>that Woeginger somehow missed these papers. # # I haven't read Woeginger's 2003 article. Sure, it's entirely possible # that Woeginger has somehow missed these papers. There are gazillions of # papers published each year; it's easy to miss some. I indeed have missed these papers. Since two of them are from the crypto community, I would expect that they use probabilistic / randomized approaches. --Gerhard ___________________________________________________________ Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/
From: Woeginger Gerhard on 28 Mar 2006 06:42
Craig Feinstein <cafeinst(a)msn.com> wrote: # # Woeginger Gerhard wrote: #> Craig Feinstein <cafeinst(a)msn.com> wrote: #> # 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 write: ... for solving subset-sum "with repect to n" #> on computer X #> #> Does this mean: With respect to one particular value n? #> (A is fast for subsets of size n; it might be slow for #> subsets of other sizes). #> #> Or does this mean: With respect to all numbers n? #> (A is fast for subsets of size 1; and fast for subsets of size 2; #> and fast for subsets of size 3; and so on.) # # One particular value n, in the context of my definition. But then your argument is clearly WRONG. There is a famous result by Meyer auf der Heide, that designs a non-uniform algorithm for n-item SUBSET-SUM with a polynomial time complexity of 2*(n^4)*log(n) + O(n^3): =========== Friedhelm Meyer auf der Heide: A polynomial linear search algorithm for the n-dimensional knapsack problem. Journal of the ACM 31(3): 668-676 (1984) =========== The work of Meyer auf der Heide yields (for example) the existence of an algorithm that solves every instance of SUBSET-SUM with n=1000 input numbers in at most 10^16 steps. The work of Feinstein claims that every such algorithm must use at least 2^500 steps in the worst case. Since 2^500 is much bigger than 10^16, the result of Meyer auf der Heide disproves the claim of Feinstein. --Gerhard ___________________________________________________________ Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/ |