P systems with active membranes: trading time for space

We consider recognizer P systems having three polarizations associated to the membranes, and we show that they are able to solve the PSPACE-complete problem Quantified 3SAT when working in polynomial space and exponential time. The solution is uniform (all the instances of a fixed size are solved by the same P system) and uses only communication rules: evolution rules, as well as membrane division and dissolution rules, are not used. Our result shows that, as it happens with Turing machines, this model of P systems can solve in exponential time and polynomial space problems that cannot be solved in polynomial time, unless P = SPACE.     

Solving HPP and SAT by P Systems with Active Membranes and Separation Rules

The P systems (or membrane systems) are a class of distributed parallel computing devices of a biochemical type, where membrane division is the frequently investigated way for obtaining an exponential working space in a linear time, and on this basis solving hard problems, typically NP-complete problems, in polynomial (often, linear) time. In this paper, using another way to obtain exponential working space – membrane separation, it was shown that Satisfiability Problem and Hamiltonian Path Problem can be deterministically solved in linear or polynomial time by a uniform family of P systems with separation rules, where separation rules are not changing labels, but polarizations are used. Some related open problems are mentioned.     

P Systems with Mobile Membranes

P systems with active membranes are among the central ones in membrane computing, and they were shown to be both computationally universal (able to simulate Turing machines) and computationally efficient (able to solve hard problems in polynomial time). However, in all cases, these results were obtained by making use of several powerful features, such as membrane polarization, label changing, division of non-elementary membranes, priorities, or cooperative rules. This paper contributes to the research effort of introducing a class of P systems with active membranes having none of the features mentioned above, but still preserving the power and the efficiency. The additional feature we consider instead are the operations of endocytosis and exocytosis: moving a membrane inside a neighboring membrane, or outside the membrane where it is placed. We investigate the power and the efficiency of these systems (also using membrane division) by first proving that they can simulate (with a linear slowdown and without introducing non-determinism) rewriting P systems with 2-replication, for which the universality and the possibility of solving NP-complete problems in polynomial time are known. In this way, the universality and efficiency are also obtained for our systems. We also give a direct and simple proof for the universality result – without using division rules (the proof uses nine membranes, but we do not know whether this number can be decreased).     

P systems with minimal parallelism

A current research topic in membrane computing is to find more realistic P systems from a biological point of view, and one target in this respect is to relax the condition of using the rules in a maximally parallel way. We contribute in this paper to this issue by considering the minimal parallelism of using the rules: if at least a rule from a set of rules associated with a membrane or a region can be used, then at least one rule from that membrane or region must be used, without any other restriction (e.g., more rules can be used, but we do not care how many). Weak as it might look, this minimal parallelism still leads to universality. We first prove this for the case of symport/antiport rules. The result is obtained both for generating and accepting P systems, in the latter case also for systems working deterministically. Then, we consider P systems with active membranes, and again the usual results are obtained: universality and the possibility to solve NP-complete problems in polynomial time (by trading space for time).     

Evaluating the SAT problem on P systems for different high-performance architectures

Membrane computing is an emergent research area studying the behavior of living cells to define bio-inspired computing devices, also called P systems. Such devices provide polynomial time solutions to NP-complete problems by trading time for space. The efficient simulation of P systems poses three major challenging issues: an intrinsic massive parallelism of P systems, an exponential computational workspace, and a non-intensive floating point nature. This paper analyzes the simulation of a family of recognizer P systems with active membranes that solves the satisfiability problem in linear time on three different architectures: a shared memory multiprocessor, a distributed memory system, and a manycore graphics processing unit (GPU). For an efficient handling of the exponential workspace created by the P systems computation, we enable different data policies on those architectures to increase memory bandwidth and exploit data locality through tiling. Parallelism inherent to the target P system is also managed on each architecture to demonstrate that GPUs offer a valid alternative for high-performance computing at a considerably lower cost. Our results lead to execution time improvements exceeding 310 \(\times \) and 78 \(\times \) , respectively, for a much cheaper high-performance alternative.     

Complexity of evolution in maximum cooperative P systems

We introduce a variant of P systems called maximum cooperative P systems; it consists of transition P systems with cooperative rules that evolve at each step by consuming the maximum number of objects. The problem of distributing objects to rules in order to achieve a maximum consuming evolution is studied by introducing the resource mapping problem. The decision version of this optimization problem is proved to be NP-complete. We describe a new simulation technique for the evolution of the maximum cooperative P systems based on integer linear programming. Finally we illustrate the evolution by an example.     

A polynomial alternative to unbounded environment for tissue P systems with cell division

The standard definition of tissue P systems includes a special alphabet whose elements are assumed to appear in the initial configuration of the system in an arbitrarily large number of copies. These objects reside in a distinguished place of the system, called the environment. Such potentially infinite supply of objects seems an unfair tool when designing efficient solutions to computationally hard problems in the framework of membrane computing, by performing a space–time trade-off. This paper deals with computational aspects of tissue P systems with cell division where there is no environment having the property mentioned above. Specifically, we prove that the polynomial complexity classes associated with tissue P systems with cell division and with or without environment are actually identical. As a consequence, we conclude that it is not necessary to have infinitely many copies of some objects in the initial configuration in order to solve NP–complete problems in an efficient way.     

Complexity classes in models of cellular computing with membranes

In this paper we introduce four complexity classes for cellularcomputing systems with membranes: the first and the second ones containall decision problems solvable in polynomial time by a family ofdeterministic P systems, without and with an input membrane,respectively; the third and fourth classes contain all decision problemssolvable in polynomial time by a family of non-deterministic P systems,without and with an input membrane, respectively. We illustrate theusefulness of these classes by solving two NP–completeproblems, namely HPP and SAT, in both variants of Psystems.     

The computational power of cell division in P systems: Beating down parallel computers?

We study the computational power of cell division operations in the formalframework of P systems, a mathematical model of cell-like membrane structure with regulated transport of objects (molecules) through membranes. We show that a uniformfamily of P systems with active membranes and2-division is able to solve the well-known PSPACE-complete problem QBF inlinear time. This result implies that such a family of P systems modelling celldivision is at least as powerful as so-called Second Machine Class computers. The Second Machine Class, containing most of the fundamental parallelcomputer models such as parallel RAM machines of types SIMD and MIMD, vector machinesand others, is characterized by using an exponential amount of resources(processing units) with respect to the computing time.     

Complexity aspects of polarizationless membrane systems

We investigate polarizationless P systems with active membranes working in maximally parallel manner, which do not make use of evolution or communication rules, in order to find which features are sufficient to efficiently solve computationally hard problems. We show that such systems are able to solve the PSPACE-complete problem Quantified 3-sat, provided that non-elementary membrane division is controlled by the presence of a (possibly non-elementary) membrane.     

Uniform solutions to SAT and 3-SAT by spiking neural P systems with pre-computed resources

We consider the possibility of using spiking neural P systems for solving computationally hard problems, under the assumption that some (possibly exponentially large) pre-computed resources are given in advance. In particular, we propose two uniform families of spiking neural P systems which can be used to address the NP-complete problems sat and 3-sat, respectively. Each system in the first family is able to solve all the instances of sat which can be built using n Boolean variables and m clauses, in a time which is quadratic in n and linear in m. Similarly, each system of the second family is able to solve all the instances of 3-sat that contain n Boolean variables, in a time which is cubic in n. All the systems here considered are deterministic.     

Solving multidimensional 0–1 knapsack problem by P systems with input and active membranes

Membrane systems are biologically motivated theoretical models of distributed and parallel computing. In this paper, we present a membrane algorithm to solve multidimensional 0–1 knapsack problem in linear time by recognizer P systems with input and with active membranes using 2-division. This algorithm can also be modified to solve general 0–1 integer programming problem.     

Further remark on P systems with active membranes and two polarizations

P systems (or membrane systems) are a class of distributed parallel computing devices of a biochemical type. In this paper, some restrictions on the general form of the developing rules are considered, under which it is still possible to solve NP-complete problems. We present an algorithm for deterministically deciding SAT in linear time by P systems with active membranes using two polarizations and rules of restricted versions of types (a), (c), (e). The result obtained in this paper answered an open problem proposed by Alhazov and Freund in the aspect of computing efficiency.     

Minimizing evolution-communication P systems and automata

Evolution-communication P systems are a variant of P systems allowing both rewriting rules and symport/antiport rules, thus having separated the rewriting and the communication. The purpose of this paper is to solve an open problem stated in Reference,¹⁾ namely generating the family of Turing computable sets of vectors of natural numbers instead of the family of Turing computable sets of natural numbers. The same construction also reduces the 3-membrane non-cooperative case and the 2-membrane 1-catalyst case to the 2-membrane non-cooperative case. Also, EC P automata are introduced and it is proved that 2-membrane EC P automata with a promoter can accept all recursively enumerable languages. Finally, a definition of an extended system is given, and its universality is proved using the rules of more restricted types. Artiom Alhazov: He has graduated from Mathematics and Computer Science, State University of Moldova in 2001, and is currently a Ph.D. student in Chişinăm, Moldova, and Tarragona, Spain. He has won prizes at 3 National Olympiads in Informatics and in Mathematics (1995 and 1996), participated at 8th International Olympiad in Informatics (Veszprem, Hungary, 1996). He has experience in programming and teaching, and has published 18 papers, mostly in Membrane Computing. His interests are Origami, Mathematics, Programming, Theoretical Computer Science, Formal Linguistics and Biocomputing.     

Results on catalytic and evolution-communication P systems

In this paper we give several improved universality results for two important classes of P systems: P systems with catalysts and evolution-communication P systems. First, the result from Reference,¹⁴⁾ stating that six catalysts ensure the universality, has been improved in two ways: using bistable catalysts and using moving catalysts. Specifically, the universality can be reached with one bistable catalyst and 2 usual catalysts (using five membranes), as well as with one moving catalyst and three membranes, or with two moving catalysts and only two membranes. The second part of the paper deals with evolution-communication P systems, and we also give improved universality results for this type of systems, in terms of the weight of symport/antiport rules, number of membranes, or number of catalysts. Shankara Narayanan Krishna: She is an Assistant Professor in Dept. Computer Science & Engg, IIT Bombay, India. Her research interests are Natural Computing and Formal Methods. Andrei Paun, Ph.D.: He obtained his bachelor degree in Mathematics and Computer Science from the University of Bucharest, Romania. He obtaind his Ph.D. degree in Computer Science, at University of Western Ontario, Canada, under the supervision of Prof. Dr. Sheng Yu, with the thesis “Unconventional Models of Computation: DNA and Membrane Computing”. After graduation he received a postdoctoral felloship from NSERC, Canada and after six months he accepted an assistant professor position in US at Louisiana Tech University.     

Solving the Subset-Sum problem by P systems with active membranes

We present the first membrance 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).     

The computational power of membrane systems under tight uniformity conditions

We apply techniques from complexity theory to a model of biological cellular membranes known as membrane systems or P-systems. Like Boolean circuits, membrane systems are defined as uniform families of computational devices. To date, polynomial time uniformity has been the accepted uniformity notion for membrane systems. Here, we introduce the idea of using AC ⁰-uniformity and investigate the computational power of membrane systems under these tighter conditions. It turns out that the computational power of some systems is lowered from P to NL when using AC ⁰-semi-uniformity, so we argue that this is a more reasonable uniformity notion for these systems as well as others. Interestingly, other P-semi-uniform systems that are known to be lower-bounded by P are shown to retain their P lower-bound under the new tighter semi-uniformity condition. Similarly, a number of membrane systems that are known to solve PSPACE-complete problems retain their computational power under tighter uniformity conditions.     

Spiking neural P systems with neuron division and budding

Spiking neural P systems are a class of distributed and parallel computing models inspired by spiking neurons.In this work,the features of neuron division and neuron budding are introduced into the framework of spiking neural P systems,which are processes inspired by neural stem cell division. With neuron division and neuron budding,a spiking neural P system can generate exponential work space in polynomial time as the case for P systems with active membranes.In this way,spiking neural P systems can efficie...     

Uniform solutions to SAT and Subset Sum by spiking neural P systems

We continue the investigations concerning the possibility of using spiking neural P systems as a framework for solving computationally hard problems, addressing two problems which were already recently considered in this respect: Subset Sum{\tt Subset}\,{\tt Sum} and SAT.{\tt SAT}. For both of them we provide uniform constructions of standard spiking neural P systems (i.e., not using extended rules or parallel use of rules) which solve these problems in a constant number of steps, working in a non-deterministic way. This improves known results of this type where the construction was non-uniform, and/or was using various ingredients added to the initial definition of spiking neural P systems (the SN P systems as defined initially are called here “standard”). However, in the Subset Sum{\tt Subset}\,{\tt Sum} case, a price to pay for this improvement is that the solution is obtained either in a time which depends on the value of the numbers involved in the problem, or by using a system whose size depends on the same values, or again by using complicated regular expressions. A uniform solution to 3-SAT{\tt SAT} is also provided, that works in constant time.     

The GPU on the simulation of cellular computing models

Membrane Computing is a discipline aiming to abstract formal computing models, called membrane systems or P systems, from the structure and functioning of the living cells as well as from the cooperation of cells in tissues, organs, and other higher order structures. This framework provides polynomial time solutions to NP-complete problems by trading space for time, and whose efficient simulation poses challenges in three different aspects: an intrinsic massively parallelism of P systems, an exponential computational workspace, and a non-intensive floating point nature. In this paper, we analyze the simulation of a family of recognizer P systems with active membranes that solves the Satisfiability problem in linear time on different instances of Graphics Processing Units (GPUs). For an efficient handling of the exponential workspace created by the P systems computation, we enable different data policies to increase memory bandwidth and exploit data locality through tiling and dynamic queues. Parallelism inherent to the target P system is also managed to demonstrate that GPUs offer a valid alternative for high-performance computing at a considerably lower cost. Furthermore, scalability is demonstrated on the way to the largest problem size we were able to run, and considering the new hardware generation from Nvidia, Fermi, for a total speed-up exceeding four orders of magnitude when running our simulations on the Tesla S2050 server.