О сложности задачи существования предельных циклов заданной длины

Аннотация

В работе исследуется вычислительная сложность задачи существования предельных циклов фиксированной длины \(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
Опубликовано на условиях лицензии Creative Commons Attribution 4.0 International (CC BY 4.0)

← К номеру журнала

× Issue cover