Skip to main content
2 of 2
Use a more informative presentation. Also, mention dependence on space
Emil Jeřábek
  • 2.2k
  • 14
  • 17

A Turing machine running in time $t(n)$ can be simulated by circuits of size $O(t(n)\log t(n))$; see e.g. https://courses.cs.washington.edu/courses/cse532/04sp/lect05.pdf .

More generally, a similar argument shows that a Turing machine running in time $t(n)$ and space $s(n)$ can be simulated by circuits of size $O(t(n)\log s(n))$.

Emil Jeřábek
  • 2.2k
  • 14
  • 17