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 Π2P-completeness with several intermediate problems being either NP or coNP-complete.
Formenti, E., Manzoni, L., Porreca, A. (2014). Fixed points and attractors of reaction systems. In Language, Life, Limits, 10th Conference on Computability in Europe, CiE 2014 (pp.194-203). Springer [10.1007/978-3-319-08019-2_20].
Fixed points and attractors of reaction systems
MANZONI, LUCA;PORRECA, ANTONIO ENRICO
2014
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 Π2P-completeness with several intermediate problems being either NP or coNP-complete.
| File | Dimensione | Formato | |
|---|---|---|---|
|
Paper.pdf
Solo gestori archivio
Dimensione
277.22 kB
Formato
Adobe PDF
|
277.22 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
