(Untitled)

[kalmakka]

How to solve exponential-time problems in linear time
or
Why Kalmakka should not be allowed to discuss complexity theory (esp. with _dw)

Say you have an algorithm that takes O(kn) time for some k. Wait O(n) time for Moore's law to build up, build a computer kn times as fast as those of today and solve the problem in O(1) time. Total time = O(n) + O(

Comments

[_dw]

*chuckles*

You can do even better if the exponential algorithm runs in polynomial space, as you can simply swap the old computer for a newer one every suitable increment.

Assume cost is not a factor. Then the most complex function you can solve in time t is one that requires time equivalent to the integral of the Moore's law curve between 0 and t on a single computer.

Doing that gets rid of the 2 factor in your solution - now you can solve it in n years for k=2.

[kalmakka]

Hmm.. can you? The fastest computer you will get to use is 2n/2 as fast as those of today. Even if you had such a computer from the beginning of, it would use O(2n/2) units of time to do 2n calculations.

You only save O(1) time or so, I think.

[_dw]

Say the time units are normalized so that at t+1, the fastest computer is double the speed of the one at t.

Then by waiting and running in linear time, you have to wait n time units until the computer calculates 2n with the speed it calculates 1 with the present day computer.

By switching every time unit (to relax the restriction of continuous change), assuming memory is universal and such, we get 20 + 21 + 22 + ... + 2n-1, so you get the answer a time unit earlier.

Hm, it seems you're right.