Solving a PSPACE-complete problem with cP systems

DOI10.1007/s41965-020-00064-wzbMath1469.68036OpenAlexW3104027319MaRDI QIDQ1982985

Radu Nicolescu, Alec Henderson, Michael J. Dinneen

Publication date: 14 September 2021

Published in: Journal of Membrane Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s41965-020-00064-w

zbMATH Keywords

computational complexitymembrane computingcP-systems

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Biologically inspired models of computation (DNA computing, membrane computing, etc.) (68Q07)

Related Items (6)

A sublinear Sudoku solution in cP systems and its formal verification ⋮ Formal verification of cP systems using Coq ⋮ Sublinear P system solutions to NP-complete problems ⋮ Neighbourhood message passing computation on a lattice with cP systems ⋮ Towards automated deduction in cP systems ⋮ Spiking neural P systems with polarizations and astrocytes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources
• Tissue P systems.
• Computing with membranes
• An introduction to \(\mathrm{cP}\) systems
• Formal verification of cP systems using PAT3 and ProB
• Characterizing PSPACE with shallow non-confluent P systems
• Actor-like cP systems
• Solving QSAT in sublinear depth
• Parallel Thinning with Complex Objects and Actors
• Uniform Solution of QSAT Using Polarizationless Active Membranes
• Alternation
• The Hamiltonian Cycle and Travelling Salesman Problems in cP Systems
• Membrane Computing

This page was built for publication: Solving a PSPACE-complete problem with cP systems