Sublinear P system solutions to NP-complete problems
Dinneen, Michael J., Henderson, Alec, and Nicolescu, Radu (2023) Sublinear P system solutions to NP-complete problems. Theoretical Computer Science, 958. 113848.
|
PDF (Published Version)
- Published Version
Available under License Creative Commons Attribution. Download (416kB) | Preview |
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.
Item ID: | 79085 |
---|---|
Item Type: | Article (Research - C1) |
ISSN: | 0304-3975 |
Copyright Information: | © 2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/) |
Date Deposited: | 15 Jun 2023 00:10 |
FoR Codes: | 46 INFORMATION AND COMPUTING SCIENCES > 4613 Theory of computation > 461302 Computational complexity and computability @ 100% |
SEO Codes: | 28 EXPANDING KNOWLEDGE > 2801 Expanding knowledge > 280115 Expanding knowledge in the information and computing sciences @ 100% |
Downloads: |
Total: 57 Last 12 Months: 8 |
More Statistics |