Cellular solutions to some numerical NP-complete problems: A Prolog implementation

TitleCellular solutions to some numerical NP-complete problems: A Prolog implementation
Publication TypeContributions to Book Chapters
Year of Publication2005
AuthorsCordón-Franco, A., Gutiérrez-Naranjo M. A., Pérez-Jiménez M. J., & Riscos-Núñez A.
EditorsGheorghe, M.
Book TitleMolecular Computational Models: Unconventional Approaches
ISBN Number978-1591403340
PublisherIdea Group Publishing
Pages115-149
Abstract

This chapter is devoted to the study of numerical NP-complete problems in the framework of cellular systems with membranes, also called P systems (Păun, 1998). We present efficient solutions to the Subset-Sum and the Knapsack problems. These solutions are obtained via families of P systems with the capability of generating an exponential amount of working space in polynomial time.
Besides, a simulation tool for P systems, written in Prolog, is described. As an illustrative example, a session in the Prolog simulator implementing one of the presented cellular solutions is included.

URLhttp://www.cs.us.es/~marper/investigacion/Cellularsolutions.pdf
ChapterV
DOI10.4018/978-1-59140-333-3
AttachmentSize
Cellularsolutions.pdf73.84 KB