This article does not cite any sources. (December 2009) (Learn how and when to remove this template message)
This article may require cleanup to meet Wikipedia's quality standards. The specific problem is: Incomplete definition (August 2014) (Learn how and when to remove this template message)
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 .