Solving PP-Complete and #P-Complete Problems by P Systems with Active Membranes
From MaRDI portal
Publication:5191164
DOI10.1007/978-3-540-95885-7_8zbMath1196.68087OpenAlexW2117686597MaRDI QIDQ5191164
Artiom Alhazov, Lyudmila Burtseva, Yurii Rogozhin, Svetlana Cojocaru
Publication date: 28 July 2009
Published in: Membrane Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-95885-7_8
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- Trading polarizations for labels in P systems with active membranes
- Complexity classes in models of cellular computing with membranes
- On the power of membrane division in P systems
- A fast \(P\) system for finding a balanced 2-partition
- Complexity Theory
- Computational Complexity of Probabilistic Turing Machines
- Machines, Computations, and Universality