Re: Complexity Theory for Simpletons
 From: Woeginger Gerhard <gwoegi@xxxxxxxxxxxxxxxxxxxxxx>
 Date: 28 Mar 2006 12:42:33 GMT
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 MeetintheMiddle. 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 RAMmodel.
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/
.
 References:
 Complexity Theory for Simpletons
 From: Craig Feinstein
 Re: Complexity Theory for Simpletons
 From: Craig Feinstein
 Re: Complexity Theory for Simpletons
 From: Googmeister
 Re: Complexity Theory for Simpletons
 From: Woeginger Gerhard
 Re: Complexity Theory for Simpletons
 From: David Wagner
 Re: Complexity Theory for Simpletons
 From: Craig Feinstein
 Complexity Theory for Simpletons
 Prev by Date: Re: Complexity Theory for Simpletons
 Next by Date: Re: Complexity Theory for Simpletons
 Previous by thread: Re: Complexity Theory for Simpletons
 Next by thread: New releases of the Parma Polyhedra Library
 Index(es):
Relevant Pages
