0
$\begingroup$

To represent complexity of an algorithm, Computer Scientist is used to using big-O notation.

How about complexity of boolean algebra?

Boolean algebra is commonly used in digital circuit design with using logic gates, practically useful in FPGA programming. Speaking about logic gates circuit, This topic maybe looks like Computer Engineering question, but I think it's okay to ask in Computer Science. Actually Computer Scientist and Computer Engineer doesn't need to know about Electrical Engineering at all to know about it, because logic gates already an abstraction of electrical stuff, all we just need to know is Input->Logic->Output where Input/Output are just bunch of 0 and 1.

What I mean about complexity of boolean algebra is actually complexity of logic gates circuit. As we know, if an input propagate to a logic gate for example a NOT gate, it needs time to propagate, if there's NOT gate again (more step), then more time to consume, hence that's circuit is going to complex.

Look this case for example,

  • #1 Z = NOT(X) is equivalent with
  • #2 Z = NOT(NOT(NOT(X)))
  • Where Z is output and X is an input.

first second

But they are different in complexity. Practically (eg: FPGA programming), #2 is slower than #1 due to three steps to propagate while #1 is just one step to pass.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

This is called Circuit Complexity: https://en.wikipedia.org/wiki/Circuit_complexity

The size of a circuit is the number of gates it contains and its depth is the maximal length of a path from an input gate to the output gate.

There are two major notions of circuit complexity. The circuit-size complexity of a Boolean function f is the minimal size of any circuit computing f. The circuit-depth complexity of a Boolean function f is the minimal depth of any circuit computing f.

These are usually measured in big-O notation. Since the difference in the number of gates (1 vs 3) in your example is only a constant, the two are considered the same w.r.t. big-O complexity.

Improve this answer
$\endgroup$
6
  • $\begingroup$ So Z = NOT(X) has complexity O(1) while Z = NOT(NOT(NOT(X))) has complexity O(3) ? What complexity do you mean? Circuit size complexity or circuit depth complexity? $\endgroup$
    – Muhammad Ikhwan Perwira
    Aug 21, 2022 at 0:44
  • $\begingroup$ @MuhammadIkhwanPerwira The first has size 1 and depth 1. The second has size 3 and depth 3. So in this case it doens't matter if we talk about size or depth. And furthermore, O(3) = O(1) $\endgroup$
    – Albert Hendriks
    Aug 21, 2022 at 10:02
  • $\begingroup$ So, size means total logic gates used, while depth means total steps required to produce output (cmiiw). $\endgroup$
    – Muhammad Ikhwan Perwira
    Aug 21, 2022 at 10:32
  • $\begingroup$ For example case Z = NOT(X) AND NOT(Y) where Z is output and X and Y is input. has size=3 and depth=2 (cmiiw). $\endgroup$
    – Muhammad Ikhwan Perwira
    Aug 21, 2022 at 10:36
  • 1
    $\begingroup$ @MuhammadIkhwanPerwira Your example with size=3 and depth=2 is correct. $n$ is the number of inputs. E.g. if you want to compute the xor of $n$ inputs, that can be done with a circuit of size $O(n)$ and depth $O(\log n)$. $\endgroup$
    – Albert Hendriks
    Aug 21, 2022 at 10:42

Your Answer

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

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