Newsgroups: comp.arch
Path: utzoo!henry
From: henry@zoo.toronto.edu (Henry Spencer)
Subject: Re: Compiler Costs
Message-ID: <1990Jul15.010508.28207@zoo.toronto.edu>
Organization: U of Toronto Zoology
References: <628@dg.dg.com> <1990Jul12.182552.26715@cbnewsi.att.com>
Date: Sun, 15 Jul 90 01:05:08 GMT

In article <1990Jul12.182552.26715@cbnewsi.att.com> yam@cbnewsi.att.com (toshihiko.yamakami) writes:
>> Many of the optimization problems belong to the "NP-complete" or even
>> the "Turing-uncomputable" categories...
>
>I always wonder why human beings can do 'Turing-uncomputable' computation.
>If human beings can do, why can't a program simulate it?

The answer is that human beings don't solve the entire problem, only a
subset of it.  And really, that is all you need.  Programmers do not
write arbitrary programs.  The NP-completeness or Turing-uncomputability
of an optimization problem is seldom of much interest; all it tells you
is that there is no halfway-efficient fully-optimal fully-general solution.
In practice, the fully-optimal fully-general solutions usually are only
halfway efficient anyway, and hence nobody uses them.  It's much better
to use something that sacrifices theoretical optimality or full generality
but runs fast on real input.
-- 
NFS:  all the nice semantics of MSDOS, | Henry Spencer at U of Toronto Zoology
and its performance and security too.  |  henry@zoo.toronto.edu   utzoo!henry