2026-07-22T14:06:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13677 2024-03-06T10:52:38Z ddc:004 open_access

Rice-Like Theorems for Automata Networks Gamard, Guilhem Guillon, Pierre Perrot, Kevin Theyssier, Guillaume Automata networks Rice theorem complexity classes polynomial hierarchy hardness We prove general complexity lower bounds on automata networks, in the style of Rice’s theorem, but in the computable world. Our main result is that testing any fixed first-order property on the dynamics of an automata network is either trivial, or NP-hard, or coNP-hard. Moreover, there exist such properties that are arbitrarily high in the polynomial-time hierarchy. We also prove that testing a first-order property given as input on an automata network (also part of the input) is PSPACE-hard. Besides, we show that, under a natural effectiveness condition, any nontrivial property of the limit set of a nondeterministic network is PSPACE-hard. We also show that it is PSPACE-hard to separate deterministic networks with a very high and a very low number of limit configurations; however, the problem of deciding whether the number of limit configurations is maximal up to a polynomial quantity belongs to the polynomial-time hierarchy. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Guilhem Gamard and Pierre Guillon and Kevin Perrot and Guillaume Theyssier 2021 Is Part Of LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2021.32 urn:nbn:de:0030-drops-136770 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.32 eng https://creativecommons.org/licenses/by/4.0/legalcode