标题： 对称转运/反向转运膜系统与膜分离表征 P^(#P) 显示英文标题

标题： Symport/Antiport P Systems with Membrane Separation Characterize P^(#P)

摘要： 膜系统是一种以分布式和并行方式运行的计算模型，其灵感来源于生物细胞的行为。 这些系统在嵌套的膜结构内具有可以转化的对象。 本研究集中于这类系统的特定类型，基于细胞的协同运输/反向运输通信机制。 文献中的结果表明，允许细胞分裂的此类系统可以解决PSPACE问题。 在我们的研究中，我们研究使用膜分离代替细胞分裂的系统，目前对此类系统的相关结果较为有限。 值得注意的是，已证明此类系统在多项式时间内可解决的问题都属于复杂度类P^(#P)。 通过实现一个解决MIDSAT（一个P^(#P)-完全问题）的系统，我们证明了相反的包含关系也成立，从而对具有协同运输/反向运输和膜分离的P系统可解决的问题类进行了精确表征。 此外，我们的实现使用的规则长度最多为三。 在这一限制下，已知系统能够解决NP完全问题，而将规则长度限制为二时，它们则表征P。 显示英文摘要

摘要： Membrane systems represent a computational model that operates in a distributed and parallel manner, inspired by the behavior of biological cells. These systems feature objects that transform within a nested membrane structure. This research concentrates on a specific type of these systems, based on cellular symport/antiport communication of chemicals. Results in the literature show that systems of this type that also allow cell division can solve PSPACE problems. In our study, we investigate systems that use membrane separation instead of cell division, for which only limited results are available. Notably, it has been shown that any problem solvable by such systems in polynomial time falls within the complexity class P^(#P). By implementing a system solving MIDSAT, a P^(#P)-complete problem, we demonstrate that the reverse inclusion is true as well, thus providing an exact characterization of the problem class solvable by P systems with symport/antiport and membrane separation. Moreover, our implementation uses rules of length at most three. With this limit, systems were known to be able to solve NP-complete problems, whereas limiting the rules by length two, they characterize P.