Skip to main content
added 170 characters in body
Source Link
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

Here is the basic idea. We'll take P as an example.

Given a Turing machine running in polynomial time, we construct, for each input length, a layered circuit in which each circuit represents the current configuration of the Turing machine:

  • For each cell, the contents of the cell.
  • For each cell, whether the head is there.
  • The current state of the machine.

The number of layers is the same as the polynomial upper bound on the running time, and the width of each layer (number of cells) is the maximum space used by the machine.

The initial layer is initialized directly from the input. Each other layer is constructed from the preceding layer (using the convention that once the machine halts, its configuration remains static). Finally, the output is extracted from the last layer. The construction is uniform, as the description hopefully makes clear.


This shows that you can convert Turing machines running in time $T(n)$ and space $S(n)$ to uniform circuits of size $O(T(n)S(n))$. This can likely be improved.

Here is the basic idea. We'll take P as an example.

Given a Turing machine running in polynomial time, we construct, for each input length, a layered circuit in which each circuit represents the current configuration of the Turing machine:

  • For each cell, the contents of the cell.
  • For each cell, whether the head is there.
  • The current state of the machine.

The number of layers is the same as the polynomial upper bound on the running time, and the width of each layer (number of cells) is the maximum space used by the machine.

The initial layer is initialized directly from the input. Each other layer is constructed from the preceding layer (using the convention that once the machine halts, its configuration remains static). Finally, the output is extracted from the last layer. The construction is uniform, as the description hopefully makes clear.

Here is the basic idea. We'll take P as an example.

Given a Turing machine running in polynomial time, we construct, for each input length, a layered circuit in which each circuit represents the current configuration of the Turing machine:

  • For each cell, the contents of the cell.
  • For each cell, whether the head is there.
  • The current state of the machine.

The number of layers is the same as the polynomial upper bound on the running time, and the width of each layer (number of cells) is the maximum space used by the machine.

The initial layer is initialized directly from the input. Each other layer is constructed from the preceding layer (using the convention that once the machine halts, its configuration remains static). Finally, the output is extracted from the last layer. The construction is uniform, as the description hopefully makes clear.


This shows that you can convert Turing machines running in time $T(n)$ and space $S(n)$ to uniform circuits of size $O(T(n)S(n))$. This can likely be improved.

Post Undeleted by Yuval Filmus
Post Deleted by Yuval Filmus
Source Link
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

Here is the basic idea. We'll take P as an example.

Given a Turing machine running in polynomial time, we construct, for each input length, a layered circuit in which each circuit represents the current configuration of the Turing machine:

  • For each cell, the contents of the cell.
  • For each cell, whether the head is there.
  • The current state of the machine.

The number of layers is the same as the polynomial upper bound on the running time, and the width of each layer (number of cells) is the maximum space used by the machine.

The initial layer is initialized directly from the input. Each other layer is constructed from the preceding layer (using the convention that once the machine halts, its configuration remains static). Finally, the output is extracted from the last layer. The construction is uniform, as the description hopefully makes clear.