Tissue P systems with cell division or cell separation have been proved able to solve NP-complete problems in polynomial time by trading space for time. We show that, when tissue P systems are embedded into the Euclidean space R^3, the power of division and separation decreases due to the geometrical constraints of the space and, as a result, only problems in P can be solved in polynomial time.
Tissue P systems in the Euclidean space
Luca Manzoni;
2016-01-01
Abstract
Tissue P systems with cell division or cell separation have been proved able to solve NP-complete problems in polynomial time by trading space for time. We show that, when tissue P systems are embedded into the Euclidean space R^3, the power of division and separation decreases due to the geometrical constraints of the space and, as a result, only problems in P can be solved in polynomial time.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
cover+pdf.pdf
Accesso chiuso
Tipologia:
Documento in Versione Editoriale
Licenza:
Copyright Editore
Dimensione
524.98 kB
Formato
Adobe PDF
|
524.98 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.
