Solving a PSPACE-complete problem with cP systems

DOI10.1007/S41965-020-00064-WMaRDI QIDQ1982985zbMATH OpenOpenAlexFDO

Authors Alec Henderson, Radu Nicolescu, 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)

Recommendations

• P systems attacking hard problems beyond NP: a survey
• scientific article; zbMATH DE number 2118901
• The Hamiltonian Cycle and Travelling Salesman Problems in cP Systems
• scientific article; zbMATH DE number 1583885
• Solution to PSPACE-complete problem using P systems with active membranes with time-freeness

Cites work

• scientific article; zbMATH DE number 5595162 (Why is no real title available?)
• Actor-like cP systems
• Alternation
• An introduction to cP systems
• Characterizing PSPACE with shallow non-confluent P systems
• Computing with membranes
• Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources
• Formal verification of cP systems using PAT3 and ProB
• Membrane Computing
• P systems with active membranes: Attacking NP-complete problems
• Parallel Thinning with Complex Objects and Actors
• Solving QSAT in sublinear depth
• Spiking neural P systems
• The Hamiltonian Cycle and Travelling Salesman Problems in cP Systems
• Tissue P systems.
• Uniform Solution of QSAT Using Polarizationless Active Membranes

Cited in

(7)

• A sublinear Sudoku solution in cP systems and its formal verification
• Neighbourhood message passing computation on a lattice with cP systems
• Towards automated deduction in cP systems
• Formal verification of cP systems using Coq
• Sublinear P system solutions to NP-complete problems
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Spiking neural P systems with polarizations and astrocytes

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

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