Misplaced Pages

This article does not cite any sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Lupanov representation" – news · newspapers · books · scholar · JSTOR (December 2009) (Learn how and when to remove this message)

This article may require cleanup to meet Misplaced Pages's quality standards. The specific problem is: Incomplete definition. Please help improve this article if you can. (August 2014) (Learn how and when to remove this 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 2n. The reciprocal is that:

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

Definition

The idea is to represent the values of a boolean function ƒ in a table of 2 rows, representing the possible values of the k first variables x₁, ..., ,x_k, and 2 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 ${\displaystyle |A_{p}|=s'\leq s}$. Let ƒ_i(x) = ƒ(x) iff x ∈ A_i.

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

External links

• Course material describing the Lupanov representation
• An additional example from the same course material

• Boolean algebra
• Circuit complexity