Dinneen, Michael J., Henderson, Alec, and Nicolescu, Radu (2023) Sublinear P system solutions to NP-complete problems. Theoretical Computer Science, 958. 113848.

Preview

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: 58 Last 12 Months: 6
	More Statistics