In my previous understanding, if a RAM program requires $T$ read/write operations to memory during its execution, then the runtime of this RAM program is $T$. However, as I have read some literature, I have realized that my understanding may not be correct.

For instance, there is a paper mentioning a $T$-time RAM program that can be transformed into a circuit of size $O(T^3 \log T)$. This is a result from complexity theory. However, if $T$ only represents the number of memory read/write operations, then this result is evidently incorrect because the size of the circuit when not performing read/write operations may be very large.

Therefore, what exactly $T$ represents? Thank you, everyone.

  • 1
    $\begingroup$ This uses "T-time RAM program". By my reading of it and one of it's references, they both use "T-time" to mean time (a fixed) polynomial in T (for the side doing the bulk of the computation), not proportional to T. I don't make this an answer because the paper mentioned in the second paragraph remains unknown, and it may use different definitions. $\endgroup$
    – fgrieu
    Commented Nov 20, 2023 at 16:44


Your Answer

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

Browse other questions tagged or ask your own question.