Rice-like complexity lower bounds for Boolean and uniform automata networks
<|reference_start|>Rice-like complexity lower bounds for Boolean and uniform automata networks: Automata networks are a versatile model of finite discrete dynamical systems composed of interacting entities (the automata), able to embed any directed graph as a dynamics on its space of configurations (the set of vertices, representing all the assignments of a state to each entity). In this world, virtually any question is decidable by a simple exhaustive search. We lever the Rice-like complexity lower bound, stating that any non-trivial monadic second order logic question on the graph of its dynamics is NP-hard or coNP-hard (given the automata network description), to bounded alphabets (including the Boolean case). This restriction is particularly meaningful for applications to "complex systems", where each entity has a restricted set of possible states (its alphabet). For the non-deterministic case, trivial questions are solvable in constant time, hence there is a sharp gap in complexity for the algorithmic solving of concrete problems on them. For the non-deterministic case, non-triviality is defined at bounded treewidth, which offers a structure to establish metatheorems of complexity lower bounds.<|reference_end|>
@article{goubault--larrecq2024rice-like,
    title={Rice-like complexity lower bounds for Boolean and uniform automata
  networks},
    author={Ali'enor Goubault--Larrecq, K'evin Perrot},
    journal={arXiv preprint arXiv:2409.08762},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.08762},
    primaryClass={cs.DM cs.CC cs.LO}
}