Lupanov representation

Lupanov's (k, s)-representation, named after Oleg Lupanov, is a way of representing Boolean circuits so as to show that the reciprocal of the Shannon effect. Shannon had showed that almost all Boolean functions of n variables need a circuit of size at least 2ⁿn⁻¹. The reciprocal is that:

All Boolean functions of n variables can be computed with a circuit of at most 2ⁿn⁻¹ + o(2ⁿn⁻¹) gates.

Definition

The idea is to represent the values of a boolean function ƒ in a table of 2^k rows, representing the possible values of the k first variables x₁, ..., ,x_k, and 2^n−k columns representing the values of the other variables.

Let A₁, ..., A_p be a partition of the rows of this table such that for i < p, |A_i| = s and $|A_{p}|=s'\leq s$ . Let ƒ_i(x) = ƒ(x) iff x ∈ A_i.

Moreover, let $B_{i,w}$ be the set of the columns whose intersection with $A_{i}$ is $w$ .

Lupanov representation

Definition

See also