Лупановское представительство

Лупанова ( k , s )-представление , названное в честь Олега Лупанова , — это способ представления булевых схем , чтобы показать, что эффект Шеннона обратен эффекту Шеннона . Шеннон показал, что почти для всех булевых функций от n переменных требуется схема размером не менее 2 ^н н ⁻¹ . Обратное заключается в том, что:

Все логические функции от n переменных можно вычислить с помощью схемы, состоящей не более чем из 2 ^н н ⁻¹ + о(2 ^н н ⁻¹ ) ворота.

Определение

Идея состоит в том, чтобы представить значения логической функции ƒ в таблице из 2 ^к строки, представляющие возможные значения k первых переменных x ₁ , ..., , x _k и 2 ^{n − k} столбцы, представляющие значения других переменных.

Пусть A ₁ , ..., Ap _— разбиение строк этой таблицы такое, что при i < p , | А _я | = s и $|A_{p}|=s'\leq s$.Пусть ƒ _i ( x ) = ƒ ( x ) тогда и только тогда, когда   x ∈ A _i .

Более того, пусть $B_{i,w}$ — набор столбцов, пересечение которых с $A_{i}$ является $w$.

Внешние ссылки

• Материал курса, описывающий представление Лупанова
• Дополнительный пример из того же материала курса