Runtime for many programming languages is typically analyzed either assuming each operation takes a constant amount of time, or assuming each operation takes a logarithmic amount of time in the size the the data being manipulated. From a practical perspective, this is reasonable since modern computers have essentially constant time memory access (albeit for a fixed amount of memory).

However, from a theoretical perspective, it seems to me that this is a bad assumption.

Since bits can't be stored denser than the Planck scale (which we are fast approaching), the number of bits we can store in a certain volume of space can grow at most linearly as volume grows. Further, since the speed of memory retrieval and storage is bounded by the speed of light, it makes a lot of sense to say that as the size of the data we store grows, the cost for storing and accessing it should grow. For instance, one could assume that storing and accessing the $n$th bit of data requires $\sqrt[3]{n}$ time. (Since space is 3-dimensional).

Presumably this has been discussed in the literature somewhere. Could anyone point me to some references? Have algorithms been analyzed using this model?

  • 1
    $\begingroup$ the way to deal with this is a memory hierarchy. search for external memory algorithms and cache-oblivious algorithms $\endgroup$ – Sasho Nikolov May 6 '13 at 8:05

You are totally right in your observation. If complexity analysis would be done on a Turing machine level the memory distance would be taken into account. You may use a 3 dimensional tape if you like and your analysis is on sub-polynomial level.

My Master thesis in 1990 was about the same topic. In that thesis I argued that instead of looking at the number of transistors/gates we should look at the length of the wires. Looking at it that way some seemingly smart ideas to reduce complexity break down. One example I used was Lupanov's method to represent an arbitrary function in a circuit taking $O(\frac{2^n}{n})$ gates. This is actually not much more efficient than a regular ROM when the average length of the wires is taken into account.

Things can get worse. If you consider a RAM machine where registers can be addressed from another register (pointers) and multiplication can be done in unit time, then it has been shown that PSPACE problems can be solved in polynomial time. I don't have a reference at hand, it was folklore at the time of my college years.

In answer to the question below. The crux of the method consists of (ab)using the fact that all registers are initially zero and the pointer arithmetic is used to leave the majority of registers at 0 and sparsely put a value in others. The registers now serve as a huge lookup table, without the burden of initializing the table.

On the wiki page for Pointer machine you will find a quote from Peter van Emde Boas:

an interesting theoretical model, but ... its attractiveness as a fundamental model for complexity theory is questionable. Its time measure is based on uniform time in a context where this measure is known to underestimate the true time complexity. The same observation holds for the space measure for the machine (van Emde Boas (1990) p. 35)

The referred book of Van Leeuwen most likely describes the method to solve PSPACE problems on these machines in polynomial time. You may actually want to check, because it is quite some time ago for me and the machine might also need the parallelism of the PRAM model.

  • $\begingroup$ I'd be interested in a source for your folklore. I don't see how register adressability could change anything, one may as well not use any register if adressability is important. What can probably change something is considering that one may multiply data of any size in constant time, especially if they can be stored in one memory cell or register. $\endgroup$ – AProgrammer May 6 '13 at 9:12
  • $\begingroup$ @AProgrammer I added somewhat of a reference for you. $\endgroup$ – Bryan Olivier May 6 '13 at 10:21

Usually estimations are refined only if they aren't valid in the interesting domain. Complexity theory is already a crude approximation (ignoring constant factor, ignoring all terms but one) and for interesting problem sizes considering the memory access time as constant doesn't reduce its usefulness. If you want to be more precise, taking the constant factor and some additional terms into account or the disparity in access time due to caching is probably more worthwhile. (Note that in practice the effect you are speaking will appear as a disparity in access time due to caching).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.