In the RAM model, you're allowed to do unbounded indirect access (pointers can be arbitrarily large and still fit in a single machine word).

In the Bit Complexity model (no wiki article, sorry), machine words are constant sized. So storing the address of an entry in a table of size $N$ would require $O(lg(N))$ words.

This raises the question: Are you even allowed to do a multi-word random access into a table of size $N$ when using the bit complexity model? It's a bit of a strange operation, because the machine can't "hold the jump in its head" while making it. On the other hand, it could be allowed but cost $O(lg(n))$ time instead of the RAM model's $O(1)$ time.

I realize that this is basically just a definition, with interesting things on either side, but I'm wondering what the common definition is. Is bit complexity just another way of saying "multi-tape turing machine"?

  • $\begingroup$ Why do you say "instead of $O(1)$ time"? Why would a multi-word random access be $O(1)$ time, when (if I understand you correctly) you said that a single-word random access takes $O(\lg N)$ time? $\endgroup$ – D.W. Jul 15 '14 at 6:55
  • $\begingroup$ Where do you get that $O(\log(n))$ limit from in your first sentence? There is no such limit described in the linked WP article, nor have I seen such a limit in other definitions of RAM. $\endgroup$ – FrankW Jul 15 '14 at 7:30
  • $\begingroup$ Perhaps you should take a look at this: math.uni-leipzig.de/~diem/preprints/bitcomplexity.pdf. $\endgroup$ – Yuval Filmus Jul 15 '14 at 13:26
  • $\begingroup$ @D.W. I was contrasting it against the RAM model, where getting to items in a similarly sized table was cheap because the addresses fit into a word. $\endgroup$ – Craig Gidney Jul 15 '14 at 14:08
  • $\begingroup$ @FrankW It was a misunderstanding between the size of allowed arithmetic and the size of allowed pointers. I've edited it. $\endgroup$ – Craig Gidney Jul 15 '14 at 14:12

According to Fürer's paper, the underlying complexity model is a Turing machine without random access, or equivalently, Boolean circuits. So no random access is allowed. Check also Diem's writeup on the subject.

  • $\begingroup$ Another source which is very careful regarding the model is the very recent arxiv.org/pdf/1407.3360v1.pdf, which proves a Fürer-type bound for integer multiplication with a simpler algorithm (and better constants). $\endgroup$ – Yuval Filmus Jul 18 '14 at 2:50

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.