# Proposals

Jason Marshall jason@george.localnet
Fri, 30 Jun 2000 08:10:52 -0700 (PDT)

```> I don't know why this provides such concern.

> Spiders have 8 legs.  Beetles have 6.  I have a box
> containing spiders and beetles.  In performing a
> count I come up with 46 legs.  Now the question is
> how many beetles and spiders are in the box?
>
> The logical expression for this is:
> 8s + 6b = 46.  Now to set the conditions.  The
> number of spiders or beetles must be equal to or
> greater than zero.

But this is a simple equation with only two free
variables.  Do you honestly think this scales up
to 100 free variables?

Are you familliar with the Travelling Salesman
problem?

A frugal salesman needs to visit 100 cities to
peddle his wares.  In the interests of improving
his margins a little, he sets about to determine
the optimal path he can take between the cities,
such that he drives the fewest miles possible to
visit all the cities.

It has been proven mathematically that this is an
N*P complete problem, meaning there is no way
to solve the problem in less time than it takes
to calculate all possible routes and pick the
shortest one.

For a hundred choices, that's 100 factorial.
Now, take a program ten million lines long (these
do exist, contrary to your earlier claim that they
don't.  Windows 2000, for instance, is over 50
million lines of code).  Assume one 'choice' per
ten lines of code, and you have a million factorial,
or a number bigger than a modern computer could

This is the sort of monumental task someone trying
to write a 'perfect' compiler faces.  This is why
most people resort to 'hill climbing' algorithms
(if you're trying to get to the top of the mountain
via an almost-but-not-quite-shortest route, you
pick the direction that is the steepest incline in
your vicinity, which gains you altitude faster),
or other greedy algorithms, which frequently get
within ten percent of the optimal solution in
a small amount of time.

Now do you understand the sabre-rattling?

Regards,
Jason Marshall

```