It is known that the complexity class P is equivalent to the class of problems decided by polynomial-time uniform familiy of circuits. When stating the complexity of algorithms as this family of circuits, this complexity is usually stated in terms of the depth and size of the circuit. What I have not understood well is why the authors don't include the complexity of the Turing machine constructing the circuits as well. This seems an important part of the overall algorithm. Could somebody clear this up for me?

In particular im interested in this question in the context of quantum circuits. When implementing a quantum algorithm usually this is expressed as a quantum circuit, and quantum algorithms papers report the complexity in terms of the depth. Why not consider the complexity of the classical computer that has to construct the circuit in the first place? Can the complexity of contructing the circuit be bigger than that of running the circuit itself?


1 Answer 1


At one level, the answer to "why not" is "because that's not the definition". In mathematics, we define certain concepts and then explore them.

At another level, it's because such a variation would not add any new knowledge or create any new concepts. In particular, consider the following two versions of what you wrote:

  1. There is a single Turing machine $T$ for all input sizes. In particular, on input $x$, we let $n$ be the length of the input, run $T(1^n)$, let $C_n$ be its output, and feed $x$ as input to the circuit $C_n$.

    Then this model is exactly a uniform model of circuit complexity. It is polynomially equivalent to other standard uniform models of computation (e.g., Turing machines).

  2. There is one Turing machine $T_n$ for each input size $n$. In particular, on input $x$, we let $n$ be the length of the input, run $T_n(1^n)$, let $C_n$ be its output, and feed $x$ as input to the circuit $C_n$.

    Then this model is polynomially equivalent to non-uniform circuit models, i.e., to standard non-uniform models of computation.

So either way, we don't obtain something new; we obtain something that is equivalent to existing definitions and concepts.

Related: What is the difference between a collection of Turing Machines and a family of Circuits?, Proof that uniform circuit families can efficiently simulate a Turing Machine, Circuits vs Turing Machines in the "nonuniform model of computation", https://cs.stackexchange.com/a/110787/755, https://en.wikipedia.org/wiki/Advice_(complexity), https://en.wikipedia.org/wiki/Circuit_complexity#Uniformity, https://en.wikipedia.org/wiki/P/poly

  • $\begingroup$ I don't think this answers my question. What I meant was that when we want to compute the complexity of a uniform circuit family, we compute the size of the circuits and the depths. This is reasonable as the runtime of the circuit will depend on this parameters. Why not consider the time it takes for the TM to construct the circuit also as part of the complexity? after all, in practice we also need to run the TM when we are solving a problem (as when running quantum circuits for example). $\endgroup$
    – Apo
    Sep 28, 2022 at 1:34
  • $\begingroup$ @Apo, Ahh, got it. I think it would help if you stated that in the question. It wasn't clear from the question that this was what you were asking. In particular, the standard model for circuit complexity is a non-uniform model, so if you are interested in a uniform model of circuit complexity, it would help to state that in the question, and also to specify the specific model and where you encountered it. The seminal paper (Borodin, On Relating Time and Space to Size and Depth) does count the space used by the TM. $\endgroup$
    – D.W.
    Sep 28, 2022 at 2:08
  • $\begingroup$ Wikipedia's exposition also requires that the TM be resource-bounded: en.wikipedia.org/wiki/Circuit_complexity#Uniformity $\endgroup$
    – D.W.
    Sep 28, 2022 at 2:09

Your Answer

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

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