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).


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


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.

| cite | improve this answer | |
  • 6
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Feb 9 '16 at 8:37

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.