Given an algorithm A for computing binary function $f$. Assuming that A runs in time $t(n)$, what could we say about the size of the minimal Boolean circuit C that calculates f? I think that it implies that there exists a non-RAM Turing Machine that runs in $\leq(t(n))^2$, and hence there exists a Boolean circuit of size $\leq(t(n))^4$ that computes $f$. Am I right? Also, could we say any better?


1 Answer 1


A Turing machine running in time $t(n)$ can be simulated by circuits of size $O(t(n)\log t(n))$; see e.g. https://courses.cs.washington.edu/courses/cse532/04sp/lect05.pdf .

More generally, a similar argument shows that a Turing machine running in time $t(n)$ and space $s(n)$ can be simulated by circuits of size $O(t(n)\log s(n))$.

  • $\begingroup$ And TM itself can simulate in time $(t(n))^2$ Random Access Machine that runs in time $t(n)$, so overall we got that to simulate $t(n)$ algorithm you need circuit size $O((t(n))^2\log t(n))$. Is that right? $\endgroup$
    – Dudi Frid
    Commented Jun 23 at 3:43
  • $\begingroup$ I suppose. But I am not really familiar with simulations of RAM. $\endgroup$ Commented Jun 23 at 6:36
  • $\begingroup$ @DudiFrid I would expect a direct RAM $\rightarrow$ circuit translation can be more efficient than RAM $\rightarrow$ TM $\rightarrow$ circuit. But RAM models also can differ, e.g. words can have constant size or dependent on the input. $\endgroup$
    – rus9384
    Commented Jun 26 at 20:10

Your Answer

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

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