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 .
Emil Jeřábek
- 2.2k
- 14
- 17