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?
Best known algorithm to best Boolean Circuit upper bound
Dudi Frid
- 221
- 1
- 3
- 21