4
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$
    – Chandra Chekuri
    Commented Apr 7, 2013 at 22:27

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks. So let me check that I understand this. The idea is that Cook-Levin gives an algorithm A_n (x) , that given an n-bit input x, A_n(x) simulates the computation of M on x through circuits. The idea is that A_n(x) it-self can be built as a polynomial sized-circuit. I get this right? $\endgroup$
    – John Smith
    Commented Apr 8, 2013 at 7:07
  • $\begingroup$ 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)$. $\endgroup$
    – Kaveh
    Commented Apr 8, 2013 at 10:44
  • $\begingroup$ 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. $\endgroup$
    – Kaveh
    Commented Apr 8, 2013 at 10:47
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.