Complexity, Computability, and Cryptography with Reaction Systems

This thesis investigates Reaction Systems, a bio-inspired computational framework modelling the qualitative dynamics of biochemical reactions. Through the three perspectives of complexity, computability, and cryptography, it explores both the theoretical foundations and potential applications of this model within the broader context of natural computing. The first part analyses the complexity of the dynamics of resource-bounded Reaction Systems, where the number of reactants and inhibitors is limited. Despite these constraints, most dynamical problems—such as the existence of fixed points, attractors, and cycles—remain computationally intractable, while a notable subclass, the additive systems, admits polynomial-time algorithms. The second part introduces Pure Reaction Automata, an extension of Reaction Systems allowing multiplicities and removing permanence. These automata are shown to accept all recursively enumerable languages, while their deterministic variant computes all recursive functions. A further restriction leads to Chemical Pure Reaction Automata, revealing that the non-deterministic version retains Turing completeness, whereas the deterministic one does not. The third part establishes a connection between Reaction Systems and cryptographic Boolean functions, defining Evolutionary Boolean Reaction Systems, an evolutionary framework that evolves highly nonlinear and balanced Boolean functions expressed in Disjunctive Normal Form. This method achieves competitive results to state-of-the-art genetic algorithms while maintaining interpretability and diversity. Overall, the thesis contributes to the theory of Natural Computing by linking the study of Reaction Systems with broader questions in complexity theory, computation, and cryptographic design.