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