# 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 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/

.

**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

- 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):