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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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$ 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$– rus9384Commented Jun 26 at 20:10