首页> 外文会议>International conference on membrane computing >Active Membranes, Proteins on Membranes, Tissue P Systems: Complexity-Related Issues and Challenges
【24h】

Active Membranes, Proteins on Membranes, Tissue P Systems: Complexity-Related Issues and Challenges

机译:活性膜,膜上的蛋白质,组织P系统:与复杂性相关的问题和挑战

获取原文

摘要

We resume computational complexity aspects of several models of membrane systems, namely P systems with active membranes, P systems with proteins on membranes and tissue P systems both with membrane separation and membrane division. A sequence of common issues is studied in relation to these P system models, and 16 open problems are stated in the text. We question the role of families of P systems and their necessity to solve computationally hard problems in polynomial time. For each P system model we focus on conditions guaranteeing the polynomial equivalence of families of P systems and Turing machines. The ability of P systems to solve NP/co-NP-complete problems in polynomial time (trading space for time) is a very popular issue. Interesting characterizations of the borderline between tractability and intractability, i.e., P/NP, have been recently shown. Similarly important, although less popular, is the relation between NP/co-NP and further classes as PP, the polynomial hierarchy PH and PSPACE. Several models of P systems has been shown to characterize the class PSPACE which itself characterizes parallel computations with an unlimited number of processors but a limited propagation of data between them.
机译:我们恢复膜系统的几种模型的计算复杂性方面,即具有活性膜的P系统,具有膜上蛋白质的P系统和具有膜分离和膜分裂的组织P系统。研究了与这些P系统模型相关的一系列常见问题,并在本文中指出了16个未解决的问题。我们质疑P系统族的作用以及它们在多项式时间内解决计算难题的必要性。对于每个P系统模型,我们集中于保证P系统和图灵机族的多项式等价的条件。 P系统在多项式时间(时间交易空间)中解决NP / co-NP完全问题的能力是一个非常受欢迎的问题。最近已经显示了在易处理性和难处理性之间的边界即P / NP的有趣特征。同样不重要的是NP / co-NP与其他类(如PP),多项式层次结构PH和PSPACE之间的关系,尽管不那么受欢迎。已经显示了几种P系统模型来表征PSPACE类,该类本身可以表征并行计算,处理器数量不受限制,但它们之间的数据传播有限。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号