A Linear-Time Solution to the Knapsack Problem Using P Systems with Active Membranes

Description

Up to now, P systems dealing with numerical problems have been rarely considered in the literature. In this paper we present an effective solution to the Knapsack problem using a family of deterministic P systems with active membranes using 2-division. We show that the number of steps of any computation is of linear order, but polynomial time is required for pre-computing resources.

Abstract

Ministerio de Ciencia y Tecnología TIC2002-04220-C03-01

Additional details