7
$\begingroup$

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)$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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).

Improve this answer
$\endgroup$
7
  • $\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$
    – user35837
    Mar 31, 2017 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, 2017 at 13:26
  • $\begingroup$ Definitely yes, provide some missing point or detail in a proof, so that I can work on them. $\endgroup$
    – user35837
    Mar 31, 2017 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, 2017 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$
    – user35837
    Mar 31, 2017 at 13:50

Your Answer

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