|This article does not cite any references or sources. (December 2009)|
||This article may require cleanup to meet Wikipedia's quality standards. The specific problem is: Incomplete definition. (August 2014)|
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 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.
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 x ∈ Ai.
Moreover, let be the set of the columns whose intersection with is .