Skip to main content
2 of 4
added 16 characters in body
Dudi Frid
  • 221
  • 1
  • 3
  • 21

Best known algorithm to best Boolean Circuit upper bound

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

Dudi Frid
  • 221
  • 1
  • 3
  • 21