Computationally Hard Problems Addressed Through P Systems

Abstract

In this chapter we present a general framework to provide efficient solutions to decision problems through families of cell-like membrane systems constructed in a semi-uniform way (associating with each instance of the problem one P system solving it) or a uniform way (all instances of a decision problem having the same size are processed by the same system). We also show a brief compendium of efficient semi-uniform and uniform solutions to hard problems in these systems, and we explicitly describe some of these solutions.