首页> 外文会议>Membrane computing >Solving PP-Complete and #P-Complete Problems by P Systems with Active Membranes

【24h】

Solving PP-Complete and #P-Complete Problems by P Systems with Active Membranes

机译：用主动膜的P系统解决PP完全和#P完全问题

获取原文

获取原文并翻译 | 示例

页面导航

摘要
著录项
相似文献
相关主题

摘要

Membrane computing is a formal framework of distributed parallel multiset processing. Due to massive parallelism and exponential space some intractable computational problems can be solved by P systems with active membranes in a polynomial number of steps. In this paper we generalize this approach from decisional problems to the computational ones, by providing a solution of a #P-complete problem, namely to compute the permanent of a binary matrix. The implication of this result to the PP complexity class is discussed and compared to known results about NP ∪ co - NP.

机译：膜计算是分布式并行多集处理的正式框架。由于大量的并行性和指数空间，一些具有活动膜的P系统可以通过多项式步数解决一些棘手的计算问题。在本文中，我们通过提供#P完全问题的解决方案，即计算二进制矩阵的永久性，将这种方法从决策问题推广到计算问题。讨论了该结果对PP复杂度类别的含义，并将其与有关NP∪co-NP的已知结果进行了比较。

著录项

来源
《Membrane computing》|2008年|108-117|共10页
会议地点 Edinburgh(GB);Edinburgh(GB)
作者
Artiom Alhazov; Liudmila Burtseva; Svetlana Cojocaru; Yurii Rogozhin;
展开▼
作者单位

Academy of Sciences of Moldova Institute of Mathematics and Computer Science Academiei 5, MD-2028, Chisinau, Moldova;

Academy of Sciences of Moldova Institute of Mathematics and Computer Science Academiei 5, MD-2028, Chisinau, Moldova;

Academy of Sciences of Moldova Institute of Mathematics and Computer Science Academiei 5, MD-2028, Chisinau, Moldova;

Academy of Sciences of Moldova Institute of Mathematics and Computer Science Academiei 5, MD-2028, Chisinau, Moldova Rovira i Virgili University Research Group on Mathematical Linguistics Pl. Imperial Tarraco 1, 43005 Tarragona, Spain;

展开▼
会议组织
原文格式 PDF
正文语种 eng
中图分类混合集成电路;
关键词

相似文献

外文文献
中文文献
专利

1. An Extended Membrane System with Active Membranes to Solve Automatic Fuzzy Clustering Problems [J] . Peng Hong, Wang Jun, Shi Peng, International Journal of Neural Systems . 2016,第3期

机译：具有主动膜的扩展膜系统可解决自动模糊聚类问题
2. Solving the N-Queens problem using dP systems with active membranes [J] . Buno Kelvin C., Cabarle Francis George C., Calabia Marj Darrel, Theoretical computer science . 2018,第期

机译：使用具有活跃膜的DP系统解决N-QUEENS问题
3. Accelerated execution of P systems with active membranes to solve the N-queens problem [J] . Maroosi Ali, Muniyandi Ravie Chandren Theoretical computer science . 2014,第Null期

机译：加速执行带有活性膜的P系统以解决N皇后问题
4. Solving PP-Complete and #P-Complete Problems by P Systems with Active Membranes [C] . Artiom Alhazov, Liudmila Burtseva, Svetlana Cojocaru, International Workshop on Membrane Computing . 2009

机译：通过具有活跃膜的P系统解决PP完成和＃P-Theument问题
5. Molecular mechanisms of membrane-active peptides in model lipid systems by temperature dependent Fourier transform infrared (FTIR) and polarized attenuated total reflectance (PATR)-FTIR spectroscopy. [D] . Kearns, Amy Elizabeth. 1997

机译：通过温度依赖性傅立叶变换红外光谱（FTIR）和偏振衰减全反射（PATR）-FTIR光谱分析模型脂质系统中膜活性肽的分子机理。
6. Virtual microscopy system at Chinese medical university: an assisted teaching platform for promoting active learning and problem-solving skills [O] . Yanping Tian, Wengang Xiao, Chengren Li, 2014

机译：中国医科大学的虚拟显微镜系统：辅助教学平台可促进主动学习和解决问题的能力
7. Solving multidimensional 0-1 Knapsack problem by P systems with input and active membranes [O] . Linqiang Pan, Carlos Martin-Vide 2008

机译：通过具有输入和活动膜的p系统解决多维0-1背包问题
8. Development of a P System with Active Membranes Applying Membrane Creation Techniques [R] . Das, D. 2006

机译：应用膜生成技术开发活性膜p系统

Solving PP-Complete and #P-Complete Problems by P Systems with Active Membranes

摘要

著录项

相似文献

相关主题

期刊订阅