# Why does a polynomial-time language have a polynomial-sized circuit?

I wish to understand why P is a subset of PSCPACE, that is why a polynomial-time langauge does have a polynomial-sized circuit. I read many proofs like this one here on page 2-3, but all the proofs use the same technique used in the Cook-Levin theorem to convert the computation of M on an n-bit input x to a polynomial sized circuit.

What I don't understand is that the resulting circuit is dependent on the input x, because what is being converted into a circuit is the computation of M on the specific input x. By definition of PSIZE, the same circuit must work for all the inputs in a fixed length, and thus is not dependent on one specific input.

So how is the process of creating a poly-sized circuit family for a poly-time deterministic Turing machine works exactly?

• If you look at the construction the string $x$ is used as a variable; the construction does not look at the bit values and treats $x_1,x_2,...,x_n$ as variables. Hence the circuit works for all strings $x$ of the same length. – Chandra Chekuri Apr 7 '13 at 22:27

Cook-Levin gives one circuit for all inputs of a given size. So although the circuit depends on the input $x$, it only depends on the size of the input. So given TM $M$ with running time $t$, and a number $n$ (the size of input), Cook-Levin gives a circuit $C_n$ of size roughly $t^2$ that solves the problem on all inputs of size $n$. The circuit $C_n$ does not depend on what are the bits of the input for $M$, however we need to know the numbers of input bits as that is going to be the number of input bits for the circuit.
• Yes, $A_n(x)$ is simply $A(x)$ restricted to inputs of size $n$. If the space complexity of $A$ is $s(n)$ and the time complexity is $t(n)$, we make a table with $t(n)$ rows and $s(n)$ columns for the configurations. The ith row is the ith configuration. Each cell in the table can be computed from fixed number of cells in the row above it in the table. The top row is the starting configuration with $x$ on the tape. We also add a simple last part that checks if the configuration in the bottom row is accepting. The size of this circuit is roughly $s(n)t(n)$. – Kaveh Apr 8 '13 at 10:44
• For the top row we will use the wires for the bits of the input $x$. Whatever we put in $x$, the top row will be the corresponding initial configuration. – Kaveh Apr 8 '13 at 10:47