1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 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 ♦
    Nov 20 at 16:44

0

Reset to default

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.

Browse other questions tagged or ask your own question.