Can someone explain (or provide a reference for) how to show that uniform circuit families can efficiently simulate Turing machines? I have only seen them discussed in terms of specific complexity classes (e.g., $\mathbf{P}$ or $\mathbf{NC}$). I would like to see how uniform circuit families is a strong enough model for universal, efficient computation.
4
-
$\begingroup$ What does it mean for uniform circuit families to be strong enough for universal, efficient computation? I truly have no idea. $\endgroup$– Yuval FilmusCommented Apr 13, 2020 at 18:32
-
$\begingroup$ Yea, I guess this is what I'm getting at. If it's a nonsense question, then great...I just want to understand why it's nonsense. We can define a poly-time uniform family of circuits (i.e there is a poly-time TM that on input $1^n$ outputs the description of the circuit). Turns out this captures the power of complexity class P. Can we give an analogous description which gives a definition of the complexity class R? $\endgroup$– tigercub97Commented Apr 13, 2020 at 18:41
-
$\begingroup$ Yes. There is a Turing machine that on input $n$ outputs the description of a circuit. $\endgroup$– Yuval FilmusCommented Apr 13, 2020 at 18:44
-
$\begingroup$ Do you have a reference with more detail on this? You gave a definition but how do you prove that a language is in R iff such a uniform family exists? (I'm concerned that such a TM has too much power.) Also, for a language $L \in \mathrm{TIME}(n)$, can we show that the resulting uniform family has size $poly(\mathrm{TIME}(n))$? Thanks for your time! $\endgroup$– tigercub97Commented Apr 13, 2020 at 18:56
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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.
answered Apr 13, 2020 at 18:20
-
$\begingroup$ I guess I'm hung up on the definition of such uniform families. You can define poly-time uniform circuit families with a single, poly-time Turing machine that outputs a circuit per input size. What is the equivalent definition for universal uniform circuit families? $\endgroup$ Commented Apr 13, 2020 at 18:28
-
$\begingroup$ There are several definitions of uniformity. You can check out this paper, for example. $\endgroup$ Commented Apr 13, 2020 at 18:30
$\begingroup$
$\endgroup$
Let us prove the following theorem:
A language $L$ is decidable if there is a Turing machine $T$ that on input $n$ outputs a circuit for $L \cap \{0,1\}^n$.
$\Longrightarrow$ Suppose that $L$ is decidable. Given $n$, we can compute $L \cap \{0,1\}^n$. We can then construct a circuit for the corresponding Boolean function.
$\Longleftarrow$ Suppose that there is a Turing machine $T$ than on input $n$ outputs a circuit for $L \cap \{0,1\}^n$. To decide $L$, given an input $x$, run $T(|x|)$ to get a circuit for $L \cap \{0,1\}^{|x|}$, and run it on $x$ to determine whether $x \in L$.
answered Apr 13, 2020 at 18:59