A linear solution of Subset Sum problem by using membrane creation

TitleA linear solution of Subset Sum problem by using membrane creation
Publication TypeJournal Papers
Year of Publication2005
AuthorsGutiérrez-Naranjo, M. A., Pérez-Jiménez M. J., & Romero-Campero F. J.
Journal TitleLecture Notes in Computer Science
ISBN Number978-3-540-26298-5
PublisherSpringer
Place PublishedAmsterdam, The Netherlands
Volume3561
Pages258-267
Abstract

Membrane Computing is a branch of Natural Computing which starts from the assumption that the processes taking place in the compartmental structure of a living cell can be interpreted as computations. In this framework, the solution of NP problems is obtained by generating an exponential amount on workspace in polynomial time and using parallelism to check simultaneously all the candidates to solution. We present a solution to the Subset Sum problem for P systems where new membranes are generated from objects.

KeywordsCellular complexity classes, Membrane computing, Natural computing, Subset Sum Problem.
URLhttp://www.springerlink.com/content/hhk559wmhg0qw87l/?p=16f5fea3cb444987a8c6641261510c68&pi=26
ISSN Number0302-9743
DOI10.1007/b137289