Logarithmic SAT Solution with Membrane Computing

Journal Publication ResearchOnline@JCU
Nicolescu, Radu;Dinneen, Michael J.;Cooper, James;Henderson, Alec;Liu, Yezhou
Abstract

P systems have been known to provide efficient polynomial (often linear) deterministic solutions to hard problems. In particular, cP systems have been shown to provide very crisp and efficient solutions to such problems, which are typically linear with small coefficients. Building on a recent result by Henderson et al., which solves SAT in square-root-sublinear time, this paper proposes an orders-of-magnitude-faster solution, running in logarithmic time, and using a small fixed-sized alphabet and ruleset (25 rules). To the best of our knowledge, this is the fastest deterministic solution across all extant P system variants. Like all other cP solutions, it is a complete solution that is not a member of a uniform family (and thus does not require any preprocessing). Consequently, according to another reduction result by Henderson et al., cP systems can also solve k-colouring and several other NP-complete problems in logarithmic time.

Journal

Axioms

Publication Name

N/A

Volume

11

ISBN/ISSN

2075-1680

Edition

N/A

Issue

N/A

Pages Count

19

Location

N/A

Publisher

MDPI

Publisher Url

N/A

Publisher Location

N/A

Publish Date

N/A

Url

N/A

Date

N/A

EISSN

N/A

DOI

10.3390/axioms11020066