Sublinear P system solutions to NP-complete problems

Dinneen, 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

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