膜计算系统求解计算困难问题综述

摘要

在膜计算领域,一个备受关注的问题是证明各种膜系统模型能否在多项式时间内解决计算困难问题.然而一个重要的事实是,许多能够求解NP完全问题的膜系统模型甚至可以在多项式时间内解决PSPACE完全问题,有的模型可以刻画P#P(该复杂类被推测为严格包含在PSPACE中).文章主要介绍几类可以有效求解计算困难问题的膜系统,包括活性膜膜系统、膜上带蛋白膜系统、组织膜系统、带膜分裂的同向/反向规则膜系统以及脉冲神经膜系统;概述了这些膜系统模型的计算复杂性,指出了一些可以提高膜系统计算能力的特性,最后给出膜系统中存在的一些公开问题.