Informally, algorithm is just a series of steps to solve some problem. To be more formal, an algorithm transform inputs into desired output.

So what exactly are steps? They are just “some basic operations”

And to do those computations, we can use Boolean Circuits

$\land$ and $\lor$ or $\lnot$ not

“Solve the problem” → Complete the function

“Basic Steps” → AND/OR/NOR operations

Boolean Circuits

To implement those basic operations, we could use boolean circuits

DAG

we could use DAG - Direct Acyclic Graph - to represent the circuits

A (n, m, s) boolean circuit is a DAG with n + s vertices

n: number of variables

m: number of outputs

s: size of gates

• Exactly n of these vertices are labeled as input x[0], x[1], ... x[n-1]
• The other s vertices are “Gates” (AND/OR/NOT)
• Each fate is labeled as an $\land$ or $\lor$ or a $\lnot$
  • Each AND gate has exactly 2 incoming edges
  • Each OR gate has 2 in-edges
  • Each NOT gate has 1 in-edge
• m of the gates are labeled as outputs y[0], y[1], ..., y[m-1]

Example: