Roger posted:
> http://www.cbi.umn.edu/oh/pdf.phtml?id=317
This is an interesting article; here's a passage that really highlights how the
insights of the past become the common sense of
the present:
Frana: The idea of time being the most important complexity
measure seems rather straightforward to me now
because I've heard it and read it several places, but
it apparently wasn't.
Cook: I think time was an important measure. It was Alan
Cobham who was trying to think of some intrinsic
measure like "work," but in fact his theorem was about
the characterization of polynomial time, so that was
the thing he talked about-time. Time seemed to be
the most obvious measure of complexity. Certainly space
memory was also considered right from the start.
Before reading this, it never even occurred to me that there could be other
measures of complexity than "time to solve the
problem". It was "obvious".
Now that I think about it, though, I can lift 1 lb weight 5 feet in 10 seconds,
and I can do the same with a 100 lb weight; but
even though the time is the same, I wouldn't say the problems are "equally
difficult". I wonder if there's an equivalent measure
for "computational work".
-Dan
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
