6
$\begingroup$

When I work on an algorithm to solve a computing problem, I often experience that speed can be increased by using more memory, and memory usage can be decreased at the price of increased running time, but I can never force the product of running time and consumed memory below a clearly palpable limit. This is formally similar to Heisenberg's uncertainty principle: the product of the uncertainty in position and the uncertainty in momentum of a particle cannot be less than a given threshold.

Is there a theorem of computer science, which asserts the same thing? I guess it should be possible to derive something similar from the theory of Turing Machines.

(I asked this question originally on StackOverflow.)

Improve this question
$\endgroup$
3
  • $\begingroup$ the tradeoff you refer to is probably related to disk vs RAM which is not distinguished in $O(n)$ measurements of memory only in TMs. however there are some models that model disk/RAM tradeoff. you might look into Cache oblivious algorithm/model. papers on cache oblivious algorithms do state algorithm times in terms of the two parameters $M$ (memory) and $D$ (disk) and the tradeoff between them. $\endgroup$
    – vzn
    Aug 7, 2013 at 17:53
  • $\begingroup$ & its not so much an uncertainty as a simple numerical tradeoff. both quantities $M$ and $D$ can be precisely expressed. $\endgroup$
    – vzn
    Aug 7, 2013 at 18:01
  • $\begingroup$ Without serious insight one cannot rule out a possiblity of such a "law" in turing machines or cannot establish it rigorously either. After all the running time of an algorithm is reduced by obtaining "information" from the data set (the data maybe sorted etc.). Everytime an observation is made, some amount of entropy is generated. Infact the act of storing data amounts to an increase in entropy. You can bring some of these ideas together. Check this paper sns.ias.edu/~tlusty/courses/InfoInBio/Papers/Szilard1929.pdf $\endgroup$
    – swarnim_narayan
    Aug 7, 2013 at 18:06

1 Answer 1

Reset to default
10
$\begingroup$

This phenomenon is known in computer science as a time-space tradeoff. For example, Ryan Williams proved that if a computer solves SAT on instances of size $n$ in time $T$ and using memory $S$ then $T \cdot S \geq n^{1.8}$. (We don't expect this to be tight.) A classical result states that when recognizing palindromes on a Turing machine, $T \cdot S = \Omega(n^2)$.

Improve this answer
$\endgroup$
7
  • $\begingroup$ How tight is the bound on SAT? If it is tight, then it seems a little counter-intuitive that an NP-complete problem could have a smaller product of T and S than a problem with a known efficient algorithm. Or maybe it just tells us that that measure isn't all that meaningful in relation to how "difficult" a problem is. $\endgroup$
    – G. Bach
    Aug 7, 2013 at 21:34
  • 3
    $\begingroup$ We don't expect it do be tight at all. If some algorithm for SAT has $T = n^c$ for some constant $c$ then P=NP, which most people don't believe. Moreover, the exponential time hypothesis states that $T \geq \alpha^n$ for some $\alpha > 1$. $\endgroup$
    – Yuval Filmus
    Aug 7, 2013 at 21:38
  • 4
    $\begingroup$ It should go without saying, but space-time tradeoffs (and similar things like area-time and size-depth tradeoffs) have NOTHING to do with Heisenberg's uncertainty principle. $\endgroup$
    – JeffE
    Aug 7, 2013 at 22:28
  • 1
    $\begingroup$ @JeffE Sure, there is no real analogy, just formal similarity: the product of two important properties of a system have a lower bound. In case of the uncertainty principle, these properties are the uncertainties of e.g. particle position and momentum, in case of algorithms, these are T and S. $\endgroup$
    – kol
    Aug 7, 2013 at 22:42
  • 2
    $\begingroup$ @kol They are not about algorithms, but about problems. Not the same thing. $\endgroup$
    – G. Bach
    Aug 8, 2013 at 2:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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