1
$\begingroup$

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"?

Improve this question
$\endgroup$
5
  • $\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, 2014 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, 2014 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, 2014 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, 2014 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, 2014 at 14:12

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\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, 2014 at 2:50

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.