Research On Computational Properties Of Membrane Systems With Proteins

Membrane computing is inspired by the biology of the cell, and is a theoretical com-puter science enterpriser, aiming to provide new computing model and algorithm abstract-ed from the cell structure and functioning. There is a wide range of application value in membrane computing, such as computer science, linguistics, graphics, systems biology and cryptography.There are two kinds of membrane systems (P systems) inspired by the proteins of cell-s in membrane systems, which are membrane systems with proteins on membranes and tissue P systems. The computational power of P systems with proteins on membranes is investigated including the universality, the computational efficiency and the computation-al complexity. The computational efficiency of tissue P systems is studied. The detailed contents are shown as follows:The computational efficiency of computing devices is a natural and well investigated topic in computer science. The computational efficiency of P systems with proteins on membranes is analyzed. By a uniform family of recognizing P systems with proteins on membranes, the QSAT problem can be solved in linear time and all the instances of the problem with the same size can be processed by the same P system.In order to eliminate the impact of the response error in the actual chemical and bio-logical phenomena, a protein system is constructed where the rules are used in a minimally parallel way. As for this issue, the computational universality and efficiency of P systems with proteins on membranes are considered in minimal parallelism of using the rules. This minimal parallelism still leads to universality. With element membrane division rules, P sys-tems with proteins in minimal parallelism could solve NP-complete problems in polynomial time.In order to eliminate the influence of the time error in biochemical reactions, robust systems is introduced, called as time-free membrane systems with proteins, which always produce the same results independently from the execution times of the rules. It is possible to get universality for the time-free P systems with proteins on membranes. And the systems could provide a uniform solution for the NP-complete problem in polynomial steps.The number of reachable states for each protein will affect computational power of membrane systems. For this reason, the computing power of flip-flop P systems with pro-teins on membranes is studied. In this kind of systems, the proteins on membranes are al-ways moved in a restricted manner, by allowing at most two states for each protein. A family of flip-flop P systems with proteins on membranes with elementary membrane division is developed. They could solve NP-complete problem in polynomial time. The universality of time-free flip-flop P systems with proteins on membranes is also investigated.In the framework of membrane computing, the computing power of protein P systems with division rules only operating on elementary membranes has not been yet characterized precisely. The computational efficiency of P systems with proteins on membranes with only elementary membrane division is investigated. It is shown that P systems with proteins on membranes and elementary division rules are sufficient to solve PP (Probabilistic Polyno-mial) problems in linear time.The upper bounded power of membrane systems will be lowered under tight uniform conditions. For this issue, the computational complexity of the P systems with proteins on membranes is investigated under AC0and L uniformities conditions. Moreover, the computational complexity theory is introduced to characterize the model in terms of the set of problems. It is proved that the model characterizes NL in the semi-uniform and uniform case.Tissue P systems with cell separation has a significant difference in specific techniques for designing solutions to concrete NP-complete problems with cell division. The computa-tional efficiency of tissue P systems with cell separation is investigated. This model has the ability of generating an exponential amount of workspace in linear time by cell separation. Additionally, it is proved that this model can efficiently provide a uniform solution in a polynomial-time for Vertex Cover problem.