Energy-based P systems have been recently introduced as P systems in which the amount of energy consumed and/or manipulated during computations is taken into account. In this paper we consider conservative computations performed by energy-based P systems, that is, computations for which the amount of energy entering the system is the same as the amount of energy leaving it. We show that conservative computations naturally allow to define an NP-hard optimization problem, here referred to as MIN STORAGE, and a corresponding NP-complete decision problem, CONSCOMP. Finally, we present a polynomial time 2-approximation algorithm for MIN STORAGE
Leporati, A., Zandron, C., Mauri, G. (2005). Conservative Computations in Energy-based P Systems. In Membrane Computing: 5th International Workshop (pp.344-358). Springer-Verlag [10.1007/978-3-540-31837-8_22].
Conservative Computations in Energy-based P Systems
LEPORATI, ALBERTO OTTAVIO;ZANDRON, CLAUDIO;MAURI, GIANCARLO
2005
Abstract
Energy-based P systems have been recently introduced as P systems in which the amount of energy consumed and/or manipulated during computations is taken into account. In this paper we consider conservative computations performed by energy-based P systems, that is, computations for which the amount of energy entering the system is the same as the amount of energy leaving it. We show that conservative computations naturally allow to define an NP-hard optimization problem, here referred to as MIN STORAGE, and a corresponding NP-complete decision problem, CONSCOMP. Finally, we present a polynomial time 2-approximation algorithm for MIN STORAGE
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
