# How to relate circuit size to the running time of Turing machine

Define, $M_{[x,c]}$ as the deterministic Turing machine that operates as follows on an input $y$. The machine treats $x$ as a deterministic program, and simulates $x$ on input $y$. At the same time the machine runs a counter that stops its execution after steps $|y|^c$. If the machine accepts before the counter stops, then it accepts; otherwise, it rejects.

Let $f(i,c)$ be the smallest natural number so that $M_{[i,c]}$makes a mistake on the input $y$. Then, if $P \neq NP$ is true, the function $f(i,c)$ is always defined.

Theorem: Suppose that there are infinite number of $i$ for which there exists a $c$ so that $$f(i,c) > 2^{2^{|i|+c}}$$ Then, for infinitely many $n$, SAT has circuit size $n^{O(\log n)}$.

Proof: Let $i>1$ and $c$ be so that $$f(i,c) > 2^{2^{|i|+c}}$$ Define $n = 2^{|i|+c-1}$. Note, that $c$ is at most $\log n$. Then, $M_{[i,c]}$ on all $y$ of length $n$ is correct, since $y \leq 2^n = 2^{2^{|i|+c-1}} < f(i,c)$. The size of the circuit that simulates this Turing machine on inputs of length $n$ is polynomial in $|i|$, $n$, and the running time of the machine. The machine, by definition, runs in time $|y|^c \leq n^c \leq n^{\log n}$

I am not getting this part. Can anyone explain this (to specify, “The size of the circuit that simulates this Turing machine on inputs of length $n$ is polynomial in $|i|$, $n$, and the running time of the machine” in the quote)? (So the question is how can we relate the running time of Turing machine to the size of the circuit.)

The idea is that you can compute configuration $c_i$ from configuration $c_{i-1}$ by examining the contents of 3 adjacent cells, and if the head of the machine is there, update them accordingly. It's rather technical to write formally, but it's a generally simple proof (See "Computational complexity" by Arora and Barak for a proof).