An Approach to Computational Complexity in Membrane Computing

摘要

Abstract. In this paper we present a theory of computational complexity in the framework of membrane computing. Polynomial complexity classes in recognizer membrane systems and capturing the classical deterministic and non-deterministic modes of computation, are introduced. In this context, a characterization of the relation P = NP is described.