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

DOI10.1007/978-3-540-95885-7_8MaRDI QIDQ5191164zbMATH OpenOpenAlexFDO

Authors Artiom Alhazov, Lyudmila Burtseva, Svetlana Cojocaru, Yurii Rogozhin

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) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• P Systems with Elementary Active Membranes: Beyond NP and coNP
• P systems attacking hard problems beyond NP: a survey
• P systems with active membranes: Attacking NP-complete problems
• P systems with active membranes operating under minimal parallelism
• A survey of membrane computing systems attacking hard computational problems

Cites work

• A fast \(P\) system for finding a balanced 2-partition
• Complexity classes in models of cellular computing with membranes
• Complexity Theory
• Computational Complexity of Probabilistic Turing Machines
• scientific article; zbMATH DE number 1241379 (Why is no real title available?)
• Machines, Computations, and Universality
• On the power of membrane division in P systems
• P systems with active membranes: Attacking NP-complete problems
• The complexity of computing the permanent
• Trading polarizations for labels in P systems with active membranes

Cited in

(8)

• A Prolog simulator for deterministic P systems with active membranes
• Solution to PSPACE-complete problem using P systems with active membranes with time-freeness
• scientific article; zbMATH DE number 1583885 (Why is no real title available?)
• Solving the ST-connectivity problem with pure membrane computing techniques
• Accelerated execution of P systems with active membranes to solve the N-queens problem
• A \(\Sigma_2^{\mathrm P} \cup \Pi_2^{\mathrm P}\) lower bound using mobile membranes
• Solving SAT by P Systems with Active Membranes in Linear Time in the Number of Variables
• Solving multidimensional 0-1 knapsack problem by P systems with input and active membranes

This page was built for publication: Solving PP-Complete and #P-Complete Problems by P Systems with Active Membranes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5191164)