Skip to main content
Became Hot Network Question
edited title
Link
Dudi Frid
  • 221
  • 1
  • 3
  • 21

Best known algorithm to best Boolean Circuit Deducing upper bound for Boolean Circuit size from well-known algorithms

deleted 2 characters in body; edited tags
Source Link
Dudi Frid
  • 221
  • 1
  • 3
  • 21

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?

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?

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?

added 16 characters in body
Source Link
Dudi Frid
  • 221
  • 1
  • 3
  • 21

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

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?

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?

Source Link
Dudi Frid
  • 221
  • 1
  • 3
  • 21
Loading