<p>Time complexity is often defined as the "number of operations in the worst case for a Turing machine." The monotone circuit model of computation is not the Turing time model. Thus it is not meaningful to say what the time complexity of such a circuit is.</p>

<p>On the other hand, if we view the monotone circuit model as a model of actual circuits, then one "time cost" of computation is the depth of such a circuit. Thus in that sense the time complexity of the circuit you mention is 5.3log(n).</p>

<p>Of course, in real circuits there are other factors besides "depth" that contribute to "how long it takes to do the computation." For example, the longest wire in a circuit often is bottleneck in actual VLSI computation as its larger capacitance takes longer to charge. </p>

CC BY-SA 3.0
2016-02-09T08:37:25.667Z
The question asks for the time-complexity "of the construction". While it's unclear, I took it to mean the time needed to construct the circuit, given n in unary. This sounds like a reasonable question to me. In particular, the construction is randomized polytime, and it is interesting to ask if it can be made deterministic subexponential.
Emil Jeřábek
CC BY-SA 3.0
2016-02-09T01:39:40.377Z
2016-02-09T01:39:40.377Z
Chris Blake
<p>As showed in the paper "Monotone Circuits for the Majority Function", is possible to construct a monotone boolean circuit for the majority function on n variables with size O(n^3) and depth 5.3 log(n)+ O(1).</p>

<blockquote>
  <p><a href="http://link.springer.com/chapter/10.1007/11830924_38">http://link.springer.com/chapter/10.1007/11830924_38</a></p>
</blockquote>

<p>My question is, what is the time-complexity of such constrution? (i.e., the time needed to construct the circuit, given n in unary)</p>

<cc.complexity-theory><circuit-complexity><boolean-functions><circuit-depth>
Circuity complexity: monotone circuit of Majority function
Alan Carneiro
# Circuity complexity: monotone circuit of Majority function

(Asked by: username_0 on 2016-02-06)

As showed in the paper "Monotone Circuits for the Majority Function", is possible to construct a monotone boolean circuit for the majority function on n variables with size O(n^3) and depth 5.3 log(n)+ O(1).

> <http://link.springer.com/chapter/10.1007/11830924_38>

My question is, what is the time-complexity of such constrution? (i.e., the time needed to construct the circuit, given n in unary)

**Tags:** cc.complexity-theory, circuit-complexity, boolean-functions, circuit-depth

---

## 1 answers

### Answer by username_1 on 2016-02-09. Score: -1

Time complexity is often defined as the "number of operations in the worst case for a Turing machine." The monotone circuit model of computation is not the Turing time model. Thus it is not meaningful to say what the time complexity of such a circuit is.

On the other hand, if we view the monotone circuit model as a model of actual circuits, then one "time cost" of computation is the depth of such a circuit. Thus in that sense the time complexity of the circuit you mention is 5.3log(n).

Of course, in real circuits there are other factors besides "depth" that contribute to "how long it takes to do the computation." For example, the longest wire in a circuit often is bottleneck in actual VLSI computation as its larger capacitance takes longer to charge.

> **Comments:**
> **username_2**: The question asks for the time-complexity "of the construction". While it's unclear, I took it to mean the time needed to construct the circuit, given n in unary. This sounds like a reasonable question to me. In particular, the construction is randomized polytime, and it is interesting to ask if it can be made deterministic subexponential.  

---

