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 J. Woeginger


Relevant Pages