Статья в сборнике "Математические вопросы кибернетики" №1, Москва, 1988
Авторы:Красулина Е.Г.
О сложности реализации монотонных симметрических функций алгебры логики контактными схемами
Аннотация:
Рассматривается задача реализации монотонных симметрических функций алгебры логики в классе контактных схем. Получена новая оценка для реализации любой монотонной симметрической функции контактными схемами, а именно, что сложность любой монотонной симметрической функции не превосходит по порядку n (ln n)4 / (ln ln n)2.
Ключевые слова:
контактные схемы, симметрические функции, алгебра логики, теория сложности
