Uniformity conditions for membrane systems Uncovering complexity below P

We characterise the computational complexity of biological systems to assess their utility as novel models of computation and learn how efficiently we can simulate these systems in software. In this work we focus on the complexity of biological cells by using several established models of cell behaviour collectively known as Membrane Systems or P-Systems. Specifically we focus on analysing the power of cell division and membrane dissolution using the well-established active membrane model. Inspired by circuit complexity, researchers consider uniform and semi-uniform families of recogniser membrane systems to solve problems. That is, having an algorithm that generates a specic membrane system to compute the solutions to specic instances of a problem. While the idea of uniformity for active membrane systems is not new, we pioneer uniformity conditions that are contained in P. Previously, all attempts to characterise the power of families of membrane systems used polynomial time uniformity. This is a very strong uniformity condition, sometimes too strong. We prove three major results using tighter uniformity conditions for families of recogniser active membrane systems. First, by tightening the uniformity condition slightly to log space (L) we improve a P upper-bound on a semi-uniform family of membrane systems to a NL characterisation. With new insight into the nature of semi-uniformity we explore the relation between membrane systems and problems complete for certain classes. For example, the problem STCON is NL-complete; by restricting the problem slightly it becomes L-complete. This restriction in turn suggests a restriction to the NL characterising model which produces a new, L characterising, variation of recogniser membrane systems. The second and most signicant of our results answers an open question in membrane computing: whether the power of uniform families and semi-uniform families are always equal. The answer to this question has implications beyond membrane computing, to other branches of natural computing and to circuit complexity theory. We discovered that for AC0 uniformity, the problems solved by uniform families of systems without dissolution rules or charges are a strict subset of those problems solved by AC0 semi-uniform families of the same type. Finally we present a result contributing to another open question known as the P-conjecture. We provide a surprising P characterisation of a model that can generate exponential space in linear time using cell division. The algorithms that we use to compress this exponential information are of interest to those wishing to simulate cell behaviour or implement these models in silico. Tighter uniformity conditions allow researchers to study a range of complexity classes contained in P using the language of membrane systems. We argue that our stricter denition of uniformity is a more accurate one for characterising recogniser membrane systems because it allows researchers to see more clearly the actual power of systems, while at the same time all pre-existing results for classes that contain P (e.g. PSPACE, NP) still hold.

Name dc:type.qualificationname

phd

Level dc:type.qualificationlevel

doctoral

Grantor dc:publisher.institution

National University of Ireland Maynooth

Year dc:date.issued

2010

Author dc:creator

• Murphy, Niall

• Computer Science

Language dc:language

en