Logarithmic SAT Solution with Membrane Computing
Nicolescu, Radu, Dinneen, Michael J., Cooper, James, Henderson, Alec, and Liu, Yezhou (2022) Logarithmic SAT Solution with Membrane Computing. Axioms, 11. 66.
|
PDF (Published Version)
- Published Version
Available under License Creative Commons Attribution. Download (395kB) | Preview |
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.
Item ID: | 75510 |
---|---|
Item Type: | Article (Research - C1) |
ISSN: | 2075-1680 |
Keywords: | CP systems, Logarithmic time complexity, Membrane computing, NP-complete, NP-hard, P systems, SAT |
Copyright Information: | © 2022 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https:// creativecommons.org/licenses/by/ 4.0/). |
Date Deposited: | 14 Dec 2022 03:16 |
FoR Codes: | 46 INFORMATION AND COMPUTING SCIENCES > 4613 Theory of computation > 461399 Theory of computation not elsewhere classified @ 100% |
SEO Codes: | 22 INFORMATION AND COMMUNICATION SERVICES > 2204 Information systems, technologies and services > 220404 Computer systems @ 100% |
Downloads: |
Total: 553 Last 12 Months: 6 |
More Statistics |