Complexity Theory for Simpletons
in [Theory]
|
Prev: HEAP SORT
Next: Greedy Algorithm
From: Craig Feinstein on 27 Mar 2006 12:06 "Has your paper been accepted to any peer-reviewed conferences or journals?" Yes.
From: Woeginger Gerhard on 27 Mar 2006 12:08 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.) ======================= You write: ... solving subset-sum with repect to n "on computer X" Does this mean: On your laptop X? (This would be ridiculous. Your laptop cannot even store an input for SUBSET-SUM with n=10^1000 integers.) Which computer (or computer model) did you have in mind? --Gerhard ___________________________________________________________ Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/
From: Craig Feinstein on 27 Mar 2006 13:18 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. > > ======================= > You write: ... solving subset-sum with repect to n "on computer X" > > Does this mean: On your laptop X? (This would be ridiculous. Your > laptop cannot even store an input for SUBSET-SUM with n=10^1000 > integers.) > > Which computer (or computer model) did you have in mind? > Certainly not a laptop for reasons that you pointed out. Just a theoretical computer that can take arbitrarily large input. The specifics of the model of computation are not necessary for the argument in the paper to work. > > --Gerhard > > > ___________________________________________________________ > Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/
From: Ben Pfaff on 27 Mar 2006 13:30 "Craig Feinstein" <cafeinst(a)msn.com> writes: > "Has your paper been accepted to any peer-reviewed conferences or > journals?" > > Yes. Which ones? -- "The fact is, technical people are better off not looking at patents. If you don't know what they cover and where they are, you won't be knowingly infringing on them. If somebody sues you, you change the algorithm or you just hire a hit-man to whack the stupid git." --Linus Torvalds
From: David Wagner on 27 Mar 2006 16:23
Woeginger Gerhard wrote: >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. Cute. That's demonstrably not true -- in fact, there are better algorithms. Here are several references that do better than Meet-in-the-Middle: P. Camion, J. Patarin, "The Knapsack Hash Function proposed at Crypto'89 can be broken", EUROCRYPT '91. A. Blum, A. Kalai, H. Wasserman, "Noise-Tolerant Learning, the Parity Problem, and the Statistical Query Model", STOC 2000. D. Wagner, "A Generalized Birthday Problem", CRYPTO 2002. http://www.cs.berkeley.edu/~daw/papers/genbday.html So the paper claims to prove something that is known to be false. Hmm. |