Computational Complexity of Limit Cycle Existence in Boolean Networks
Restricted by Post Classes

Drobyshev Alexander Sergeevich

Computational Complexity of Limit Cycle Existence in Boolean Networks Restricted by Post Classes

Drobyshev A. S.

Drobyshev Alexander Sergeevich

graduate student, Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, Chair of Mathematical Theory of Intelligent Systems

0009-0002-8881-8730

Received: 30 Apr 2026 Revised: 26 May 2026 Accepted: 05 Jun 2026

Published: 2026, vol. 30, issue 2, pp. 28–54

Download full text (In Russian)

Abstract

The paper studies the computational complexity of detecting limit cycles of fixed length \(k\) in Boolean networks with local functions restricted to Post classes. It is proven that the problem is NP-complete for expressive classes \(D_2\) (monotone self-dual functions), \(F_6^\infty\), and \(F_2^\infty\), while polynomial-time solvable for linear functions \(L_1\). Explicit polynomial reductions from 3-SAT preserving limit cycles of length \(k\) are constructed.

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

BibTeX

@article{IS-Drobyshev2026,
  author  = {Drobyshev, Alexander Sergeevich},
  title   = {{Computational Complexity of Limit Cycle Existence in Boolean Networks Restricted by Post Classes}},
  journal = {Intelligent Systems. Theory and Applications},
  year    = {2026},
  volume  = {30},
  number  = {2},
  pages   = {28--54},
}

AMSBIB

\Bibitem{IS-Drobyshev2026}
\by A.\,S.~Drobyshev
\paper Computational Complexity of Limit Cycle Existence in Boolean Networks Restricted by Post Classes
\jour Intelligent Systems. Theory and Applications
\yr 2026
\vol 30
\issue 2
\pages 28--54
\lang In Russian

Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue