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 FP^NP[log n] to FPSPACE(poly).

Ancestors, descendants, and gardens of Eden in reaction systems

Manzoni Luca;
2015-01-01

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 FP^NP[log n] to FPSPACE(poly).
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0304397515005009-main.pdf

Accesso chiuso

Tipologia: Documento in Versione Editoriale
Licenza: Copyright Editore
Dimensione 379.14 kB
Formato Adobe PDF
379.14 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11368/2947778
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 22
  • ???jsp.display-item.citation.isi??? 16
social impact