Let's say that I have a digital circuit made up of XOR and AND gates.

Is there any way to describe the complexity of that circuit?

I could just use the total number of gates, but gates being in parallel are not quite the same thing as them being in series when things like latency are concerned.

Also, if at all relevant to an answer for the above, in my particular case, AND is much more costly of an operation than XOR (AND is multiplication where XOR is addition), so should be waited more heavily ideally.

If that last constraint doesn't fit into an established complexity metric for circuits, that is totally fine, and I'm still interested in an answer without that information taken into account.


  • $\begingroup$ Is circuit complexity not what you're looking for? $\endgroup$ – David Richerby Apr 21 '16 at 4:18
  • $\begingroup$ it's hard to tell. If i have some circuit like (A and B) xor (A and B and C) can circuit complexity give me some sort of value or measure of how complex that circuit is? Does it account for the fact that the A and ... can be factored out to make the circuit A and (B xor (B and C)), or is that up to me to give it a minimal circuit if I want a minimal measure? $\endgroup$ – Alan Wolfe Apr 21 '16 at 4:23
  • $\begingroup$ As with all forms of complexity, you distinguish between the measure of a specific circuit/algorithm and the measure of a function/problem, which is the minimum measure of any circuit/algorithm that implements/solves it. $\endgroup$ – David Richerby Apr 21 '16 at 5:23
  • $\begingroup$ To answer your question: Sure. There are many ways to measure complexity. To help us narrow things down, what properties do you want your measure to have? How will you evaluate potential answers? What do you want to use it for? (I previously told you about multiplicative complexity, in a previous answer. Is there some reason why they isn't a suitable answer to this question?) $\endgroup$ – D.W. Apr 22 '16 at 1:46
  • $\begingroup$ That is actually a good point. Saying "depth 7 and 51 gates" is a pretty decent metric. I wasn't sure what else was out there so wanted to see if there was anything more precise. For insurance, putting all 1s through a circuit of homomorphic encryption over the integers will give you a value that seemed like it would be a good gauge of circuit complexity (use plain text 1 value), but in practice something about it seems off. Higher numbers sometimes take less time to compute in my situation. What you recommend seems like an acceptable (and standard!) metric though (: $\endgroup$ – Alan Wolfe Apr 22 '16 at 2:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.