Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Lupanov representation
open-in-new
<p>Lupanov's (<i>k</i>, <i>s</i>)-representation, named after <a href="/facts/Oleg_Lupanov/IaIGc8FE">Oleg Lupanov</a>, is a means of representing <a href="/facts/Boolean_circuit/TwhfJp0q">Boolean circuits</a> to demonstrate an asymptotically tight upper bound on the <a href="/facts/Circuit_complexity/6EzA9Tty">circuit size</a> (i.e., the number of gates) needed to represent a <a href="/facts/Boolean_function/uT7E8pqC">Boolean function</a>. <a href="/facts/Claude_Shannon/EremsCws">Claude Shannon</a> showed that almost all <a href="/facts/Boolean_function/uT7E8pqC">Boolean functions</a> of <i>n</i> variables need a circuit of size at least 2<i>n</i><i>n</i>−1. Lupanov's (<i>k</i>, <i>s</i>)-representation shows that all Boolean functions of <i>n</i> variables can be computed with a circuit of 2<i>n</i><i>n</i>−1 + o(2<i>n</i><i>n</i>−1) gates. </p>