Given an algorithm A for computing binary function $f$. Assuming that A runs in time $t(n)$, what could we say about the lengthsize 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?
Became Hot Network Question