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

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

Mathematics Subject Classification ID

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

A $\Sigma_2^P \cup \Pi_2^P$ Lower Bound Using Mobile Membranes

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