{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,16]],"date-time":"2026-02-16T09:34:29Z","timestamp":1771234469103,"version":"3.50.1"},"reference-count":56,"publisher":"World Scientific Pub Co Pte Ltd","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Neur. Syst."],"published-print":{"date-parts":[[2025,11]]},"abstract":"<jats:p> Spiking Neural P Systems are parallel and distributed computational models inspired by biological neurons, emerging from membrane computing and applied to solving computationally difficult problems. This paper focuses on the computational complexity of such systems using neuron division rules and colored spikes for the SAT problem. We prove a conjecture stated in a recent paper, showing that enhancing the model with an input module reduces computing time. Additionally, we prove that the inclusion of budding rules extends the model\u2019s capability to solve all problems in the complexity class PSPACE. These findings advance research on Spiking Neural P Systems and their application to complex problems; however, whether both budding rules and division rules are required to extend these methods to problem domains beyond the NP class remains an open question. <\/jats:p>","DOI":"10.1142\/s0129065725500352","type":"journal-article","created":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T05:41:35Z","timestamp":1745991695000},"source":"Crossref","is-referenced-by-count":3,"title":["On the Computational Complexity of Spiking Neural Membrane Systems with Colored Spikes"],"prefix":"10.1142","volume":"35","author":[{"given":"Antonio","family":"Grillo","sequence":"first","affiliation":[{"name":"Dipartimento di Informatica, Sistemistica e Comunicazione, Universit\u00e0 degli Studi di Milano-Bicocca, Viale Sarca 336\/14 Milano 20126, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2163-7639","authenticated-orcid":false,"given":"Claudio","family":"Zandron","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica, Sistemistica e Comunicazione, Universit\u00e0 degli Studi di Milano-Bicocca, Viale Sarca 336\/14 Milano 20126, Italy"}]}],"member":"219","published-online":{"date-parts":[[2025,4,30]]},"reference":[{"key":"S0129065725500352BIB001","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1693"},{"key":"S0129065725500352BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00659-X"},{"key":"S0129065725500352BIB003","first-page":"279","volume":"71","author":"Ionescu M.","year":"2006","journal-title":"Fund. Inf."},{"issue":"1","key":"S0129065725500352BIB004","first-page":"213","volume":"73","author":"P\u0103un G.","year":"2006","journal-title":"Fund. Inf."},{"key":"S0129065725500352BIB005","doi-asserted-by":"publisher","DOI":"10.1142\/S0129065709002002"},{"key":"S0129065725500352BIB006","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-022-09917-y"},{"key":"S0129065725500352BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/s41965-024-00147-y"},{"key":"S0129065725500352BIB008","doi-asserted-by":"publisher","DOI":"10.1007\/s41965-024-00156-x"},{"key":"S0129065725500352BIB009","doi-asserted-by":"publisher","DOI":"10.1142\/S0129065718500132"},{"key":"S0129065725500352BIB010","doi-asserted-by":"publisher","DOI":"10.1142\/S0129065720500495"},{"key":"S0129065725500352BIB011","doi-asserted-by":"publisher","DOI":"10.1142\/S0129065720500422"},{"key":"S0129065725500352BIB012","doi-asserted-by":"publisher","DOI":"10.1142\/S0129065720500641"},{"key":"S0129065725500352BIB013","doi-asserted-by":"publisher","DOI":"10.1142\/S012906572250037X"},{"key":"S0129065725500352BIB014","doi-asserted-by":"publisher","DOI":"10.1142\/S0129065720500550"},{"key":"S0129065725500352BIB015","doi-asserted-by":"publisher","DOI":"10.1142\/S0129065722500368"},{"key":"S0129065725500352BIB016","doi-asserted-by":"publisher","DOI":"10.1142\/S0129065725500078"},{"key":"S0129065725500352BIB017","doi-asserted-by":"publisher","DOI":"10.1142\/S0129065724500217"},{"key":"S0129065725500352BIB018","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2025.113194"},{"key":"S0129065725500352BIB019","doi-asserted-by":"publisher","DOI":"10.1142\/S0129065724500357"},{"key":"S0129065725500352BIB020","doi-asserted-by":"publisher","DOI":"10.1007\/s41965-024-00166-9"},{"key":"S0129065725500352BIB021","doi-asserted-by":"publisher","DOI":"10.1142\/S0129065724500503"},{"key":"S0129065725500352BIB022","first-page":"1","volume":"7","author":"Yu W.","year":"2024","journal-title":"J. Membrane Comput."},{"key":"S0129065725500352BIB023","doi-asserted-by":"publisher","DOI":"10.1142\/S0129065724500230"},{"key":"S0129065725500352BIB024","doi-asserted-by":"publisher","DOI":"10.3233\/ICA-2007-14301"},{"key":"S0129065725500352BIB025","doi-asserted-by":"publisher","DOI":"10.1016\/j.neunet.2009.04.003"},{"key":"S0129065725500352BIB026","doi-asserted-by":"publisher","DOI":"10.1142\/S0129065720500276"},{"key":"S0129065725500352BIB027","doi-asserted-by":"publisher","DOI":"10.1142\/S0129065721500143"},{"key":"S0129065725500352BIB028","doi-asserted-by":"publisher","DOI":"10.1142\/S012906572450062X"},{"key":"S0129065725500352BIB029","doi-asserted-by":"publisher","DOI":"10.1142\/S012906572250023X"},{"key":"S0129065725500352BIB030","doi-asserted-by":"publisher","DOI":"10.1142\/S0129065724500369"},{"key":"S0129065725500352BIB031","doi-asserted-by":"publisher","DOI":"10.1142\/S0129065724500394"},{"key":"S0129065725500352BIB032","doi-asserted-by":"publisher","DOI":"10.1142\/S0129065724500345"},{"key":"S0129065725500352BIB033","doi-asserted-by":"publisher","DOI":"10.1142\/S0129065720500719"},{"key":"S0129065725500352BIB034","doi-asserted-by":"publisher","DOI":"10.1007\/s41965-022-00092-8"},{"key":"S0129065725500352BIB035","doi-asserted-by":"publisher","DOI":"10.1007\/s41965-023-00128-7"},{"key":"S0129065725500352BIB036","first-page":"75","volume":"6","author":"P\u0103un G.","year":"2001","journal-title":"J. Automata Languages Combin."},{"key":"S0129065725500352BIB037","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2006001"},{"key":"S0129065725500352BIB038","doi-asserted-by":"publisher","DOI":"10.1007\/s41965-020-00031-5"},{"key":"S0129065725500352BIB039","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-010-9189-x"},{"key":"S0129065725500352BIB040","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2017.06.008"},{"key":"S0129065725500352BIB041","doi-asserted-by":"publisher","DOI":"10.1155\/2018\/3745210"},{"key":"S0129065725500352BIB042","doi-asserted-by":"publisher","DOI":"10.1007\/s41965-019-00017-y"},{"key":"S0129065725500352BIB043","doi-asserted-by":"publisher","DOI":"10.1109\/TCDS.2017.2785332"},{"key":"S0129065725500352BIB044","doi-asserted-by":"publisher","DOI":"10.1007\/s41965-022-00108-3"},{"key":"S0129065725500352BIB045","doi-asserted-by":"publisher","DOI":"10.1007\/s41965-024-00153-0"},{"key":"S0129065725500352BIB046","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59126-6"},{"key":"S0129065725500352BIB047","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-56196-2"},{"issue":"5","key":"S0129065725500352BIB048","first-page":"459","volume":"5","author":"Leporati A.","year":"2009","journal-title":"Int. J. Unconvent. Comput."},{"key":"S0129065725500352BIB049","first-page":"195","volume-title":"Proc. 4th Brainstorming Week on Membrane Computing","volume":"1","author":"Chen H.","year":"2006"},{"key":"S0129065725500352BIB050","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77312-2_21"},{"key":"S0129065725500352BIB051","doi-asserted-by":"publisher","DOI":"10.1007\/s11432-011-4303-y"},{"key":"S0129065725500352BIB052","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-008-9081-0"},{"key":"S0129065725500352BIB053","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.01.019"},{"key":"S0129065725500352BIB054","first-page":"361","volume-title":"Membrane Computing","author":"Wang J.","year":"2011"},{"key":"S0129065725500352BIB055","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0162882"},{"key":"S0129065725500352BIB056","first-page":"348","volume-title":"Membrane Computing","author":"Sos\u00edk P.","year":"2011"}],"container-title":["International Journal of Neural Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129065725500352","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,18]],"date-time":"2025-09-18T07:09:26Z","timestamp":1758179366000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129065725500352"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,30]]},"references-count":56,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2025,11]]}},"alternative-id":["10.1142\/S0129065725500352"],"URL":"https:\/\/doi.org\/10.1142\/s0129065725500352","relation":{},"ISSN":["0129-0657","1793-6462"],"issn-type":[{"value":"0129-0657","type":"print"},{"value":"1793-6462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,30]]},"article-number":"2550035"}}