This paper analyses several problems related to finding and counting ancestor and descendant states, as well as gardens of Eden (i.e., states without predecessors) in reaction systems. The focus is on the complexity of finding and counting preimages and ancestors that are minimal with respect to cardinality. It turns out that the problems concerning gardens of Eden seem to require the presence of an NP-oracle to be solved. All the problems studied are intractable, with a complexity that ranges form FPNP[log n] to FPSPACE(poly).
Dennunzio, A., Formenti, E., Manzoni, L., Porreca, A. (2015). Ancestors, descendants, and gardens of Eden in reaction systems. THEORETICAL COMPUTER SCIENCE, 608, 16-26 [10.1016/j.tcs.2015.05.046].
Ancestors, descendants, and gardens of Eden in reaction systems
DENNUNZIO, ALBERTOPrimo
;MANZONI, LUCA
;PORRECA, ANTONIO ENRICOUltimo
2015
Abstract
This paper analyses several problems related to finding and counting ancestor and descendant states, as well as gardens of Eden (i.e., states without predecessors) in reaction systems. The focus is on the complexity of finding and counting preimages and ancestors that are minimal with respect to cardinality. It turns out that the problems concerning gardens of Eden seem to require the presence of an NP-oracle to be solved. All the problems studied are intractable, with a complexity that ranges form FPNP[log n] to FPSPACE(poly).
| File | Dimensione | Formato | |
|---|---|---|---|
|
Paper.pdf
accesso aperto
Tipologia di allegato:
Submitted Version (Pre-print)
Dimensione
200.24 kB
Formato
Adobe PDF
|
200.24 kB | Adobe PDF | Visualizza/Apri |
|
pubblicazione6.pdf
Solo gestori archivio
Tipologia di allegato:
Publisher’s Version (Version of Record, VoR)
Dimensione
379.14 kB
Formato
Adobe PDF
|
379.14 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.
