
Lupanov representation
Encyclopedia
Lupanov's-representation, named after Oleg Lupanov
, is a way of representing Boolean circuit
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
of size at least 2nn−1. The reciprocal is that:
Let A1, ..., Ap be a partition of the rows of this table such that for i < p, |Ai = s and
.
Let ƒi(x) = ƒ(x) iff
x ∈ Ai.
Moreover, let
be the set of the columns whose intersection with
is
.
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 2nn−1. The reciprocal is that:
All Boolean functions of n variables can be computed with a circuit of at most 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

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 ∈ Ai.
Moreover, let


