Why does a polynomial-time language have a polynomial-sized circuit?
Pergunta
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?
Solução
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.
Outras dicas
Intuitively, a polynomial size problem needs at least a polynomial sized circuit because each step in the algorithm/circuit requires a certain amount of time. If the circuit could verify an element of the language in less than polynomial time, then an algorithm could be made to do so too.