# Deducing upper bound for Boolean Circuit size from well-known algorithms

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?

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))$$.
• 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? Commented Jun 23 at 3:43
• @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. Commented Jun 26 at 20:10