Intelligent Systems.
Theory and Applications

(Intellektual'nye Sistemy. Teoriya i Prilozheniya)

On the Complexity of the Limit-Cycle Existence Problem for a Prescribed Length

Abstract

We study the computational complexity of the limit-cycle existence problem for a fixed length \(k\) in Boolean networks with the parallel update scheme and local functions restricted to classes of Post’s lattice. For every fixed \(k\geqslant 2\), a complete complexity classification is obtained. The problem is shown to be NP-complete for every closed class containing at least one of the classes \(D_2\), \(F_2^\infty\), or \(F_6^\infty\). For all remaining closed classes, the problem is polynomial-time solvable.

Keywords: Boolean networks, limit cycles, Post's lattice, computational complexity, classification, NP-completeness.

BibTeX
@article{IS-Drobyshev-Bokov2026,
  author  = {Drobyshev, Alexander Sergeevich and Bokov, Grigoriy Vladimirovich},
  title   = {{On the Complexity of the Limit-Cycle Existence Problem for a Prescribed Length}},
  journal = {Intelligent Systems. Theory and Applications},
  year    = {2026},
  volume  = {30},
  number  = {4},
  pages   = {91--94},
}
AMSBIB
\Bibitem{IS-Drobyshev-Bokov2026}
\by A.\,S.~Drobyshev, G.\,V.~Bokov
\paper On the Complexity of the Limit-Cycle Existence Problem for a Prescribed Length
\jour Intelligent Systems. Theory and Applications
\yr 2026
\vol 30
\issue 4
\pages 91--94
\lang In Russian
Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue

× Issue cover