Cellular Solutions to Some Numerical NP-Complete Problems: A Prolog Implementation

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 |Pages: 35
DOI: 10.4018/978-1-59140-333-3.ch005
OnDemand PDF Download:
$37.50

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 (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.

Complete Chapter List

Search this Book:
Reset