Cell-like and Tissue-like Membrane Systems as Recognizer Devices

Abstract

Most of the variants of membrane systems found in the literature are generally thought as generating devices. In this paper recognizer computational devices (cell–like and tissue–like) are presented in the framework of Membrane Computing, using the biological membranes arranged hierarchically, inspired from the structure of the cell, and using the biological membranes placed in the nodes of a graph, inspired from the cell inter–communication in tissues. In this context, polynomial complexity classes of recognizer membrane systems are introduced. The paper also addresses the P versus NP problem, and the (efficient) solvability of computationally hard problems, in the framework of these new complexity classes.