Статья в сборнике "Математические вопросы кибернетики" №15, Москва, 2006
Авторы:Красулина Е.Г.
О сложности реализации системы всех симметрических функций в классе контактно-вентильных схем
Аннотация:
В настоящей работе рассматривается задача реализации всех симметрических функций в классе контактно-вентильных схем. Строится асимптотически минимальная контактно-вентильная схема, реализующая все симметрические функции. Доказано, что для реализации всех симметрических функций от n переменных контактно-вентильной схемой требуется асимптотически 7 ·2n-1 элементов.
Ключевые слова:
симметрические функции, контактно-вентильные схемы, теория сложности
