Sublinear P system solutions to NP-complete problems

DOI10.1016/j.tcs.2023.113848OpenAlexW4362634829MaRDI QIDQ6038691

Alec Henderson, Radu Nicolescu, Michael J. Dinneen

Publication date: 2 May 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2023.113848

zbMATH Keywords

computational complexityNP-completemembrane computingcP systems

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Tissue P systems.
• Computing with membranes
• An introduction to \(\mathrm{cP}\) systems
• Formal verification of cP systems using PAT3 and ProB
• Solving a PSPACE-complete problem with cP systems
• Alternative representations of P systems solutions to the graph colouring problem
• A Linear–time Tissue P System Based Solution for the 3–coloring Problem
• On Efficient Algorithms for SAT
• Computational Complexity
• The Hamiltonian Cycle and Travelling Salesman Problems in cP Systems
• The complexity of theorem-proving procedures
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Sublinear P system solutions to NP-complete problems