|
О сложности реализации булевых функций в некоторых классах гиперконтактных схем
Ю. Г. Таразевич Белорусский государственный университет
Аннотация:
В классах $\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)}$ найдена физическая интерпретация в виде матриц инциденций-зацеплений контактно-трансформаторных схем.
Ключевые слова:
полином с идемпотентными переменными, гиперконтактная схема, контактный гиперграф, контактный матроид, матрица инциденций-зацеплений, контактно-трансформаторная схема.
Статья поступила: 09.02.2018 Переработанный вариант поступил: 24.12.2021
Образец цитирования:
Ю. Г. Таразевич, “О сложности реализации булевых функций в некоторых классах гиперконтактных схем”, Дискрет. матем., 34:3 (2022), 90–113; Discrete Math. Appl., 34:1 (2024), 33–50
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm1503https://doi.org/10.4213/dm1503 https://www.mathnet.ru/rus/dm/v34/i3/p90
|
Статистика просмотров: |
Страница аннотации: | 302 | PDF полного текста: | 51 | Список литературы: | 58 | Первая страница: | 24 |
|