Skip to main content
Use a more informative presentation. Also, mention dependence on space
Source Link
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://cseweb.ucsd.edu/classes/sp11/cse201A-a/ln412.pdfhttps://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))$.

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://cseweb.ucsd.edu/classes/sp11/cse201A-a/ln412.pdf .

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))$.

Source Link
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://cseweb.ucsd.edu/classes/sp11/cse201A-a/ln412.pdf .