Lupanov representation

Lupanovs ( k , s ) - representation , uppkallad efter Oleg Lupanov , är ett sätt att representera booleska kretsar för att visa att Shannoneffektens ömsesidighet . Shannon hade visat att nästan alla booleska funktioner av n variabler behöver en krets med storleken minst 2 ⁿ n ⁻¹ . Det ömsesidiga är att:

Alla booleska funktioner av n variabler kan beräknas med en krets med högst 2 ⁿ n ⁻¹ + o(2 ⁿ n ⁻¹ ) grindar.

Definition

Tanken är att representera värdena för en boolesk funktion ƒ i en tabell med 2 ^k rader, som representerar de möjliga värdena för de k första variablerna x ₁ , ..., , x _k och 2 ^{n − k} kolumner som representerar värdena på de andra variablerna.

Låt A ₁ , ..., A _p vara en partition av raderna i denna tabell så att för i < p , | A _i | = s och $|A_{p}|=s'\leq s$ . Låt ƒ _i ( x ) = ƒ ( x ) om x ∈ A _i .

Dessutom, låt $B_{i,w}$ vara mängden av kolumner vars skärningspunkt med $A_{i}$ är $w$ .

externa länkar