The proof of $P\subseteq P_{\\poly}$, Let $M$ is a Turing machine with $T(n)$ is running time and goal here is to design a boolean circuit of size $O(T(n))$ (for more detail see Arora and Barak page no -105 ).

The idea is that you can compute configuration $c_i$ from configuration $c_{i−1}$ by examining the content of 3 adjacent cells (i.e. by constant size circuit).

First Case : Let us consider that snapshot is the configuration of Turing machine i.e. requires $O(T(n))$ size.

Number of variables $x_{i,j}$, where $i$ represents a row in table and $j$ represent the colum( cook -levin reduction proof) are $T(n) \times T(n)$ many. Now when we combine the constant size circuits of all variables then size of the resultant circuit is going to be $T(n) \times T(n)$ ,which is polynomial but my goal was to design a circuit of size $O(T(n))$.

Second case : Let us consider that snapshot is machine's state and symbols read by all heads. let us consider they are $z_1,z_2 \cdots z_{T(n)}$ and size of each $z_i$ is constant string. To compute a snapshot $z_{i+1}$for this computation I need $z_i$, all old head positions and current head symbol .This all are constant size string, so I need only constant size circuit to encode the computation (current head position only depends upon the three symbol in the table in cook - levin theorem, or In other words, it is a map say $M$: $\tau^3 \mapsto \tau$, $\tau$ is a tape alphabet. So the total size of the circuit is $O(T(n))$

Question : To design a boolean circuit of size $O(T(n))$ for Turing machine $M$ with running time $T(n)$?


I'm not sure whether this can be done. However, using oblivious Turing machines, we can get a circuit of size $O(T(n)\log T(n))$. According to the proof sketch of Theorem 6.7 in the draft of Arora–Barak, given a Turing machine running in time $T(n)$ we can construct a Turing machine running in time $O(T(n)\log T(n))$ in which the head movements only depend on $n$. Such a Turing machine is known as an oblivious Turing machine. This means that you only need to update one specific cell per time step, and the result is a circuit of size $O(T(n)\log T(n))$ (details left to you).

| cite | improve this answer | |
  • $\begingroup$ In a new draft it is written that we can get a circuit of size $O(T(n))$. I am thinking like this, we have snapshots like $z_1,z_2,....z_{T(n)}$ and for each $z_i$ to $z_{i+1}$, I have a constant size circuit , so total size is going to be $O(T(n)). $\endgroup$ – Shiv Mar 31 '17 at 12:36
  • $\begingroup$ Well, I don't treat book drafts, or even books, as the bible sent down from heaven. I need to see a proof or a reference before I believe whatever's written there. Your proof idea is attractive, but it is missing some crucial details. $\endgroup$ – Yuval Filmus Mar 31 '17 at 13:26
  • $\begingroup$ Definitely yes, provide some missing point or detail in a proof, so that I can work on them. $\endgroup$ – Shiv Mar 31 '17 at 13:31
  • $\begingroup$ You didn't explain what your snapshots are, and how you compute $z_{i+1}$ from $z_I$ using a constant size circuit. At any rate, if you have concrete ideas, perhaps you should update this question or ask a new question, rather than us having this discussion in the comments. $\endgroup$ – Yuval Filmus Mar 31 '17 at 13:46
  • $\begingroup$ A snapshot is machine's state and symbol read by all heads. For second question $z_i$ snapshot depends upon the three cells directly above it (it is a map from $\tau^3 $ to $\tau$) , which is constant so it can be encoded by constant size circuit $\endgroup$ – Shiv Mar 31 '17 at 13:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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