Lupanov's (k, s)-representation, named after Oleg Lupanov, is a means of representing Boolean circuits to demonstrate an asymptotically tight upper bound on the circuit size (i.e., the number of gates) needed to represent a Boolean function. Claude Shannon showed that almost all Boolean functions of n variables need a circuit of size at least 2nn−1. Lupanov's (k, s)-representation shows that all Boolean functions of n variables can be computed with a circuit of 2nn−1 + o(2nn−1) gates.
Definition
The idea is to represent the values of a boolean function ƒ in a table of 2k rows, representing the possible values of the k first variables x1, ..., ,xk, and 2n−k columns representing the values of the other variables.
Let A1, ..., Ap be a partition of the rows of this table such that for i < p, |Ai| = s and | A p | = s ′ ≤ s {\displaystyle |A_{p}|=s'\leq s} . Let ƒi(x) = ƒ(x) iff x ∈ Ai.
Moreover, let B i , w {\displaystyle B_{i,w}} be the set of the columns whose intersection with A i {\displaystyle A_{i}} is w {\displaystyle w} .