EN
О вычислительной сложности задачи существования предельных циклов в булевых сетях с ограничениями из решётки Поста
Дробышев А. С.
Получена: 30.04.2026 Доработана: 26.05.2026 Принята: 05.06.2026
Опубликована: 2026 год, том 30, выпуск 2, С. 28–54
Аннотация
В статье исследуется вычислительная сложность задачи существования предельных циклов фиксированной длины \(k\) в булевых сетях с локальными функциями, ограниченными классами из решётки Поста. Доказано, что задача является NP-полной для выразительных классов \(D_2\) (монотонные самодвойственные функции), \(F_6^\infty\) и \(F_2^\infty\), а для класса линейных функций \(L_1\) полиномиально разрешима. Получены явные полиномиальные редукции из задачи 3-SAT с сохранением предельных циклов длины \(k\).
Ключевые слова: булевы сети, предельные циклы, решётка Поста, вычислительная сложность, NP-полнота.
BibTeX
@article{IS-Drobyshev2026,
author = {Дробышев, Александр Сергеевич},
title = {{О вычислительной сложности задачи существования предельных циклов в булевых сетях с ограничениями из решётки Поста}},
journal = {Интеллектуальные системы. Теория и приложения},
year = {2026},
volume = {30},
number = {2},
pages = {28--54},
}
AMSBIB
\RBibitem{IS-Drobyshev2026}
\by А.\,С.~Дробышев
\paper О вычислительной сложности задачи существования предельных циклов в булевых сетях с ограничениями из решётки Поста
\jour Интеллектуальные системы. Теория и приложения
\yr 2026
\vol 30
\issue 2
\pages 28--54