Re: Complexity Theory for Simpletons

Craig Feinstein <cafeinst@xxxxxxx> 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. If you think I'm lying, then just
# read Woeginger's 2003 article cited in my paper


No, no, no, no, no.

Woeginger's 2003 article has NOTHING to do with the discussion
in this thread.

===========================
All algorithms in this 2003 article are uniform algorithms in
the RAM-model.

The model of computation in Feinstein's paper is unspecified.

===========================
In the 2003 article, the running time of an algorithm A is its
**ASYMPTOTIC** worst case running time.

Feinstein considers the number of steps for **ONE** particular
value of n.

===========================


--Gerhard


___________________________________________________________
Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/

.

Relevant Pages