Computational complexity (was Re: Normalisation)

Jon Heggland wrote:
>>>I guess not. :) I can estimate the memory use of my algorithms, but I
>>>haven't felt the need for turing tape before now.
>>

> Estimating complexity on Turing machines is one thing; doing it for 
> usable programming languages / systems is slightly different. I know 
> theory, but not *all* theory. Sorry, but we can't all be omniscient.

The programming language (and the constant space/time assumptions for "int") are an abstraction -- and (like all abstractions) are leaky[1].

Will you need an 8-bit, 16-bit, 32-bit or 64-bit counter (and pointers, etc)? They take up different "constant" amounts of space, you know (and don't even start on the speed impact of the increased cache required when you deal with lots of them).

>>>>But time complexity is also different. The unary relation can be
>>>>transformed in linear time, but the string transformation requires
>>>>O(n.log(n)) steps.

On my old 6502 (8-bit registers), 16-bit multiply was a macro/subroutine and was significantly slower than 8-bit. Now you are probably using a 32-bit CPU, but if you ever go above ~4G then you will notice that 64-bit ops are _still_ slower than 32-bit ones. Our appetite for data has increased too, of course -- a single DVD is ~10^10 bytes long and HDTV probably adds another power of ten.

<oldfartmode>I dunno, kids these days with their fancy dual-core Athlons -- whatever happened to coding assembler to fit in a 256 byte page? Back then we knew the cost of a integer multiply mumble mumble <oldfartmode/>[2]

>>>I'm not versed in storing counters on turing tapes, but in my favourite
>>>programming languages, that counter takes constant space. Unless the
>>>string is *really* long (like over four billion characters)---is that
>>>what you are talking about?
>>
>>Of course. We are talking about the worst-case theoretical complexity
>>here.

>
> Sophistry. This is the kind of thing that gives theory a bad name.

No. Reality.

The Turing model isn't a perfect abstraction of the performance characteristics either, but it has some nice properties:

• not subject to vagaries of CPU/language design fashion
• doesn't "miss" anything important (i.e. it is worst case)

Engineering is the process of balancing the constraints of physical reality with cost and requirements. To do that you must _know_ the constraints.

Theory is practical, remember :-)

Misha

[1] Jon better not apply for a job at Fog Creek, me thinks (http://www.joelonsoftware.com/articles/fog0000000319.html).

[2] Oh look, I've simultaneously answered the "what is XML good for" thread too :-) Received on Tue Jul 19 2005 - 01:13:43 CEST