RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 2022, том 34, выпуск 3, страницы 90–113 (Mi dm1503)

О сложности реализации булевых функций в некоторых классах гиперконтактных схем

Ю. Г. Таразевич

Белорусский государственный университет

Аннотация: В классах $\operatorname{\text{РМ}}_F^{(n)}$ расширенных матриц над кольцами полиномов с идемпотентными переменными определены подклассы (гиперконтактных схем): $\operatorname{\text{ГС}}_F^{(n)}$ (над произвольным полем $F$) и $\operatorname{\text{ГС}}_Z^{(n)}$ (над кольцом целых чисел), — алгебраически расширяющие класс матриц инциденций контактных схем ($\operatorname{\text{КС}}^{(n)}$) и реализующие произвольные булевы функции $n$ переменных со сложностью менее $3\sqrt{2}\cdot2^{n/2}$ контактов. Такой же порядок нижней оценки получен для соответствующей функции Шеннона в классе $\operatorname{\text{ГС}}_{F_q}^{(n)}$ над произвольным конечным полем $F_q$. Для матриц класса $\operatorname{\text{ГС}}_Z^{(n)}$ найдена физическая интерпретация в виде матриц инциденций-зацеплений контактно-трансформаторных схем.

Ключевые слова: полином с идемпотентными переменными, гиперконтактная схема, контактный гиперграф, контактный матроид, матрица инциденций-зацеплений, контактно-трансформаторная схема.

УДК: 519.714.4

Статья поступила: 09.02.2018
Переработанный вариант поступил: 24.12.2021

DOI: 10.4213/dm1503


 Англоязычная версия: Discrete Mathematics and Applications, 2024, 34:1, 33–50


© МИАН, 2024