Rice-like complexity lower bounds for Boolean and uniform automata networks
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914051573940224 |
|---|---|
| author | Goubault-Larrecq, Aliénor Perrot, Kévin |
| author_facet | Goubault-Larrecq, Aliénor Perrot, Kévin |
| contents | 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 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 cliquewidth, which offers a structure to establish metatheorems of complexity lower bounds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_08762 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Rice-like complexity lower bounds for Boolean and uniform automata networks Goubault-Larrecq, Aliénor Perrot, Kévin Discrete Mathematics Computational Complexity Logic in Computer Science 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 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 cliquewidth, which offers a structure to establish metatheorems of complexity lower bounds. |
| title | Rice-like complexity lower bounds for Boolean and uniform automata networks |
| topic | Discrete Mathematics Computational Complexity Logic in Computer Science |
| url | https://arxiv.org/abs/2409.08762 |