Hi Dan
In your example about lifting weights:
you mention moving a given MASS a given DISTANCE in a given interval
of TIME
but that is not the same as comparing the WORK done in a given
interval of TIME because
WORK=.FORCE*DISTANCE
and
FORCE=.MASS*ACCELERATION
ACCELERATION=.VELOCITY/TIME
VELOCITY=.DISTANCE/TIME
So TIME is a most important measure of difficulty because by the TIME
you measure the difficulty which is what you really want to measure,
you have a lot of TIME on your hands because the amount of work that
can be done in an interval of time is a measure of the difficulty.
DIFFICULTY=.WORK/TIME
DISTANCE and TIME intervals have different magnitudes depending on
the coordinate system used in measuring but there is always an error
in these measures because we cannot know the precise momentum or
precise energy due to the uncertainty principle.
Today's atomic clocks are maintained to an accuracy of 10^-9 or 1e_9
and 1 second is defined as the duration of 9,192,631,770 cycles of
radiation corresponding to the transition between two energy levels
of the ground state of the caesium-133 atom.
Distances could be expressed in a number of wavelengths of a given
spectral line.
But you cannot know exactly what happens at a precise TIME nor
exactly at what TIME a precise event happened.
To move this to computational theory you need to consider Shannon's
information theories which show how to quantify the information in a
message and also a way to determine the limits on compressing a
message without loss of information. You would want to measure the
amount of INFORMATION (akin to force) multiplied by the PROCESSING
(akin to distance)
COMPUTAIONALwork=.INFORMATION*PROCESSING
The amount of COMPUTATIONALwork that can be done in a given time is a
measure of complexity.
COMPLEXITY=.COMPUTATIONALwork/TIME
And one more TIME - you are usually considering TIME to be a fixed
interval required for PROCESSING an instruction on a particular
machine but this can actually be varied according to the processor
clock.
Donna
[EMAIL PROTECTED]
On 12-Jul-08, at 2:40 PM, Dan Bron wrote:
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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
