Skip to main content
1 of 4
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 the minimal non-RAM Turing Machine runs in $(t(n))^2$, and hence there exists a Boolean circuit of size $(t(n))^4$ that computes $f$. Am I right? Also, could we say any better?

Dudi Frid
  • 221
  • 1
  • 3
  • 21