Cellular Solutions to Some Numerical NP-Complete Problems: A Prolog Implementation
Andrés Cordón-Franco (University of Sevilla, Spain), Miguel A. Gutiérrez-Naranjo (University of Sevilla, Spain), Mario J. Pérez-Jiménez (University of Sevilla, Spain) and Agustín Riscos-Núñez (University of Sevilla, Spain)
Copyright: © 2005
This chapter is devoted to the study of numerical NP-complete problems in the framework of cellular systems with membranes, also called P systems (Pun, 1998). The chapter presents 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 working space in polynomial time. A simulation tool for P systems, written in Prolog, is also described. As an illustration of the use of this tool, the chapter includes a session in the Prolog simulator implementing an algorithm to solve one of the above problems.