期刊
JOURNAL OF COMPUTER AND SYSTEM SCIENCES
卷 73, 期 1, 页码 137-152出版社
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jcss.2006.10.001
关键词
biological computation; P system; PSPACE; alternating Turing machine
A P system is a natural computing model inspired by information processing in cells and cellular membranes. We show that confluent P systems with active membranes solve in polynomial time exactly the class of problems PSPACE. Consequently, these P systems prove to be equivalent (up to a polynomial time reduction) to the alternating Turing machine or the PRAM computer. Similar results were achieved also with other models of natural computation, such as DNA computing or genetic algorithms. Our result, together with the previous observations, suggests that the class PSPACE provides a tight upper bound on the computational potential of biological information processing models. (C) 2006 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据