We investigate the computational complexity of deciding the occurrence of many different dynamical behaviours in reaction systems, with an emphasis on biologically relevant problems (i.e., existence of fixed points and fixed point attractors). We show that the decision problems of recognising these dynamical behaviours span a number of complexity classes ranging from FO-uniform AC^0 to Π^P_2 -completeness with several intermediate problems being either NP or coNP-complete.
Fixed points and attractors of reaction systems / Formenti, Enrico; Manzoni, Luca; Porreca Antonio, E.. - STAMPA. - 8493:(2014), pp. 194-203. ( 10th Conference on Computability in Europe, CiE 2014 Budapest, hun 2014) [10.1007/978-3-319-08019-2_20].
Fixed points and attractors of reaction systems
Manzoni Luca;
2014-01-01
Abstract
We investigate the computational complexity of deciding the occurrence of many different dynamical behaviours in reaction systems, with an emphasis on biologically relevant problems (i.e., existence of fixed points and fixed point attractors). We show that the decision problems of recognising these dynamical behaviours span a number of complexity classes ranging from FO-uniform AC^0 to Π^P_2 -completeness with several intermediate problems being either NP or coNP-complete.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
