The computational power of membrane systems under tight uniformity conditions
- Creators
- Murphy, Niall
- Woods, Damien
Abstract
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^0-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^0-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.
Additional Information
© 2011 Springer Science+Business Media B.V. Published online: 7 January 2011. We would like to thank Mario J. Pérez-Jiménez and Agustín Riscos-Núñez and the other members of the Research Group on Natural Computing at the University of Seville for interesting discussions and for hosting Niall Murphy while later versions of this article were written. We would also like to thank Antonio E. Porreca for stimulating discussions about uniformity and the anonymous reviewers for their rigour in checking Sect. 5. Niall Murphy is supported by the Irish Research Council for Science, Engineering and Technology. Damien Woods is supported by Junta de Andalucía grant TIC-581 (Spain) and National Science Foundation Grant 0832824, the Molecular Programming Project (USA).Additional details
- Eprint ID
- 23178
- Resolver ID
- CaltechAUTHORS:20110330-113729114
- Irish Research Council for Science, Engineering and Technology
- TIC-581
- Junta de Andalucía (Spain)
- 0832824
- NSF Molecular Programming Project
- Created
-
2011-03-31Created from EPrint's datestamp field
- Updated
-
2021-11-09Created from EPrint's last_modified field