1
$\begingroup$

I just started learning about circuits in Chapter 6 of "Computational Complexity". There is an emphasis on the fact this model of computation allows different circuits for different input sizes of the problem. The authors refer to this as a nonuniform model of computation.

My question is: why do we need to use circuits for this type of model? Couldn't we just as well allow for a different Turing machine for each input size? Is there some subtle reason for why we need to use circuits in order to study this model of computation?

$\endgroup$
1
$\begingroup$

You can think of Turing machines as a finite description of a function whose domain is $\mathbb{N}$. When you want to specify a different behavior for each member in a collection of finite sets which covers the entire domain, Turing machines are not the natural object to discuss.

You could obviously talk about a sequence of machines $M_n$, where $M_i$ knows how to handle strings of length $i$, and you don't care about how it behaves on different strings (such a definition of nonuniform classes would be equivalent). However, in this case, you don't really use the power of Turing machines. What you care about is only $M_k|_{\{0,1\}^k}$, which is completely determined by a computation table of size $T_k\times T_k$ where $T_k$ is the maximal running time of $M_k$ on length $k$ inputs. This table corresponds to a circuit of size $\le T_k^2$ (this can be improved), which now becomes the more natural object to discuss.

$\endgroup$

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.