{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T02:49:13Z","timestamp":1760150953111,"version":"build-2065373602"},"reference-count":23,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2022,2,8]],"date-time":"2022-02-08T00:00:00Z","timestamp":1644278400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Axioms"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.3390\/axioms11020066","type":"journal-article","created":{"date-parts":[[2022,2,9]],"date-time":"2022-02-09T01:03:40Z","timestamp":1644368620000},"page":"66","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Logarithmic SAT Solution with Membrane Computing"],"prefix":"10.3390","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2498-1002","authenticated-orcid":false,"given":"Radu","family":"Nicolescu","sequence":"first","affiliation":[{"name":"School of Computer Science, University of Auckland, Private Bag 92019, Auckland 1142, New Zealand"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9977-525X","authenticated-orcid":false,"given":"Michael","family":"Dinneen","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Auckland, Private Bag 92019, Auckland 1142, New Zealand"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9954-3280","authenticated-orcid":false,"given":"James","family":"Cooper","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Auckland, Private Bag 92019, Auckland 1142, New Zealand"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9233-5059","authenticated-orcid":false,"given":"Alec","family":"Henderson","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Auckland, Private Bag 92019, Auckland 1142, New Zealand"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9296-7408","authenticated-orcid":false,"given":"Yezhou","family":"Liu","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Auckland, Private Bag 92019, Auckland 1142, New Zealand"}]}],"member":"1968","published-online":{"date-parts":[[2022,2,8]]},"reference":[{"unstructured":"Sipser, M. (2012). Introduction to the Theory of Computation, Cengage Learning.","key":"ref_1"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/174644.174650","article-title":"Approximation algorithms for NP-complete problems on planar graphs","volume":"41","author":"Baker","year":"1994","journal-title":"J. ACM (JACM)"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"873","DOI":"10.1137\/S0097539792228228","article-title":"Fixed-parameter tractability and completeness I: Basic results","volume":"24","author":"Downey","year":"1995","journal-title":"SIAM J. Comput."},{"unstructured":"Henderson, A., Nicolescu, R., and Dinneen, M.J. (2022). Sublinear P System Solutions to NP-Complete Problems, University of Auckland. Available online: https:\/\/www.cs.auckland.ac.nz\/research\/groups\/CDMTCS\/researchreports\/download.php?selected-id=831.","key":"ref_4"},{"key":"ref_5","first-page":"205","article-title":"DNA and membrane algorithms for SAT","volume":"49","author":"Manca","year":"2002","journal-title":"Fundam. Inform."},{"doi-asserted-by":"crossref","unstructured":"Csuhaj-Varj\u00fa, E., Gheorghe, M., Rozenberg, G., Salomaa, A., and Vaszil, G. (2012). On efficient algorithms for SAT. International Conference on Membrane Computing, Springer. LNCS 7762.","key":"ref_6","DOI":"10.1007\/978-3-642-36751-9"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/s00236-006-0018-8","article-title":"Solving HPP and SAT by P systems with active membranes and separation rules","volume":"43","author":"Pan","year":"2006","journal-title":"Acta Inform."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1090","DOI":"10.1016\/j.jcss.2016.03.008","article-title":"An efficient time-free solution to SAT problem by P systems with proteins on membranes","volume":"82","author":"Song","year":"2016","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/j.ins.2016.10.046","article-title":"Tissue-like P systems with evolutional symport\/antiport rules","volume":"378","author":"Song","year":"2017","journal-title":"Inf. Sci."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1006\/jcss.1999.1693","article-title":"Computing with membranes","volume":"61","year":"2000","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_11","first-page":"75","article-title":"P systems with active membranes: Attacking NP-Complete problems","volume":"6","year":"2001","journal-title":"J. Autom. Lang. Comb."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/S0304-3975(02)00659-X","article-title":"Tissue P systems","volume":"296","author":"Pazos","year":"2003","journal-title":"Theor. Comput. Sci."},{"key":"ref_13","first-page":"279","article-title":"Spiking neural P systems","volume":"71","author":"Ionescu","year":"2006","journal-title":"Fundam. Inform."},{"doi-asserted-by":"crossref","unstructured":"Graciani, C., Riscos-N\u00fa\u00f1ez, A., P\u0103un, G., Rozenberg, G., and Salomaa, A. (2018). An Introduction to cP Systems. Enjoying Natural Computing: Essays Dedicated to Mario de Jes\u00fas P\u00e9rez-Jim\u00e9nez on the Occasion of His 70th Birthday, Springer. LNCS 11270.","key":"ref_14","DOI":"10.1007\/978-3-030-00265-7"},{"doi-asserted-by":"crossref","unstructured":"Hinze, T., Rozenberg, G., Salomaa, A., and Zandron, C. (2019). Actor-Like cP Systems. Membrane Computing, Springer. LNCS 11399.","key":"ref_15","DOI":"10.1007\/978-3-030-12797-8"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1007\/s41965-020-00064-w","article-title":"Solving a PSPACE-complete problem with cP systems","volume":"2","author":"Henderson","year":"2020","journal-title":"J. Membr. Comput."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"2345","DOI":"10.1016\/j.tcs.2010.01.019","article-title":"Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources","volume":"411","author":"Ishdorj","year":"2010","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Hinze, T., Rozenberg, G., Salomaa, A., and Zandron, C. (2019). Solving QSAT in sublinear depth. Membrane Computing, Springer. LNCS 11399.","key":"ref_18","DOI":"10.1007\/978-3-030-12797-8"},{"doi-asserted-by":"crossref","unstructured":"Freund, R., P\u0103un, G., Rozenberg, G., and Salomaa, A. (2006). A Linear Solution for QSAT with Membrane Creation. Membrane Computing, Springer. LNCS 3850.","key":"ref_19","DOI":"10.1007\/11603047"},{"doi-asserted-by":"crossref","unstructured":"Durand-Lose, J., and Margenstern, M. (2007). Uniform solution of QSAT using polarizationless active membranes. International Conference on Machines, Computations, and Universality, Springer. LNCS 4664.","key":"ref_20","DOI":"10.1007\/978-3-540-74593-8"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/s41965-019-00011-4","article-title":"Characterizing PSPACE with shallow non-confluent P systems","volume":"1","author":"Leporati","year":"2019","journal-title":"J. Membr. Comput."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"681","DOI":"10.1007\/s11047-008-9091-y","article-title":"Uniform solutions to SAT and Subset Sum by spiking neural P systems","volume":"8","author":"Leporati","year":"2009","journal-title":"Nat. Comput."},{"unstructured":"Stamm-Wilbrandt, H. (1993). Programming in Propositional Logic or Reductions: Back to the Roots (Satisfiability), Sekretariat f\u00fcr Forschungsberichte, Inst. f\u00fcr Informatik III, University of Bonn.","key":"ref_23"}],"container-title":["Axioms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2075-1680\/11\/2\/66\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:16:12Z","timestamp":1760134572000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2075-1680\/11\/2\/66"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,8]]},"references-count":23,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2022,2]]}},"alternative-id":["axioms11020066"],"URL":"https:\/\/doi.org\/10.3390\/axioms11020066","relation":{},"ISSN":["2075-1680"],"issn-type":[{"type":"electronic","value":"2075-1680"}],"subject":[],"published":{"date-parts":[[2022,2,8]]}}}