New Generation Computing, 23(2005)339-356
Ohmsha, Ltd. and Springer

Solving the Subset-Sum Problem by P Systems with Active Membranes

Mario J. PÉREZ JIMÉNEZ and Agustín RISCOS NÚÑEZ
Dpto. Ciencias de la Computacion e Inteligencia Artificial
E.T.S. Ingenieria Informática,, Universidad de Sevilla
Avda. Reina Mercedes s/n, 41012 Sevilla, España
{Mario.Perez, Agustin.Riscos-Nunez}@cs.us.es

Received 2 October 2003
Revised manuscript received 8 December 2004

Abstract

We present the first membrane computing solution to the Subset-Sum problem using a family of deterministic P systems with active membranes. We do not use priority among rules, membrane dissolution nor cooperation; it suffices to control the electrical charges of the membranes and to introduce some counters. The number of steps of any computation is of the linear order (but it is necessary a polynomial-time of precomputed resources).

Keywords:Membrane Computing, Complexity Classes, Active Membranes, Subset-Sum Problem.

[Back]