Lupanov's-representation, named after Oleg Lupanov

Oleg Lupanov

Oleg Borisovich Lupanov was a Soviet and Russian mathematician, dean of the Moscow State University's Faculty of Mechanics and Mathematics , head of the Chair of Discrete Mathematics of the Faculty of Mechanics and Mathematics .Together with his graduate school advisor, Sergey Vsevolodovich...

, is a way of representing Boolean circuit

Boolean circuit

A Boolean circuit is a mathematical model of computation used in studying computational complexity theory. Boolean circuits are the main object of study in circuit complexity and are a special kind of circuits; a formal language can be decided by a family of Boolean circuits, one circuit for each...

s 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

Circuit complexity

In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of Boolean circuits that compute them....

 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 .
Let ƒ_i(x) = ƒ(x) iff

IFF

IFF, Iff or iff may refer to:Technology/Science:* Identification friend or foe, an electronic radio-based identification system using transponders...

 x ∈ A_i.

Moreover, let be the set of the columns whose intersection with is .