Lupanov's (''k'', ''s'')-representation, named after Oleg Lupanov, is a means of representing

Boolean circuit In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible inpu ...

s to demonstrate an asymptotically tight upper bound on the circuit size (i.e., the number of gates) needed to represent a

Boolean function In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth functi ...

Claude Shannon Claude Elwood Shannon (April 30, 1916 – February 24, 2001) was an American mathematician, electrical engineer, computer scientist, cryptographer and inventor known as the "father of information theory" and the man who laid the foundations of th ...

showed that almost all

s of ''n'' variables need a circuit of size at least 2^''n''''n''⁻¹. Lupanov's (''k'', ''s'')-representation shows that all Boolean functions of ''n'' variables can be computed with a circuit of 2^''n''''n''⁻¹ + o(2^''n''''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

, A_p, =s'\leq s

. Let ''ƒ''_''i''(''x'') = ''ƒ''(''x'')

iff In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either both ...

''x'' ∈ ''A''_''i''. Moreover, let

B_{i,w}

be the set of the columns whose intersection with

A_i

w

External links

Course material describing the Lupanov representation

An additional example from the same course material
Boolean algebra Circuit complexity