Sublinear P system solutions to NP-complete problems
Journal Publication ResearchOnline@JCUDinneen, Michael J.;Henderson, Alec;Nicolescu, Radu
Abstract
Many membrane systems (e.g. P System), including cP systems (P Systems with compound terms), have been used to solve efficiently many NP-hard problems, often in linear time. However, these solutions have been independent of each other and have not utilised the theory of reductions. This work presents a sublinear solution to k-SAT and demonstrates that k-colouring can be reduced to k-SAT in constant time. This work demonstrates that traditional reductions are efficient in cP systems and that they can sometimes produce more efficient solutions than the previous problem-specific solutions.
Journal
Theoretical Computer Science
Publication Name
N/A
Volume
958
ISBN/ISSN
0304-3975
Edition
N/A
Issue
N/A
Pages Count
15
Location
N/A
Publisher
Elsevier
Publisher Url
N/A
Publisher Location
N/A
Publish Date
N/A
Url
N/A
Date
N/A
EISSN
N/A
DOI
10.1016/j.tcs.2023.113848