2021-05-202021-05-202015Song, B., Pérez Jiménez, M.d.J. y Pan, L. (2015). Efficient solutions to hard computational problems by P systems with symport/antiport rules and membrane division. BioSystems, 130 (april 2015), 51-58.0303-2647https://hdl.handle.net/11441/109102P systems are computing models inspired by some basic features of biological membranes. In this work, membrane division, which provides a way to obtain an exponential workspace in linear time, is introduced into (cell-like) P systems with communication (symport/antiport) rules, where objects are never modified but they just change their places. The computational efficiency of this kind of P systems is studied. Specifically, we present a (uniform) linear time solution to the NP-complete problem, Subset Sum by using division rules for elementary membranes and communication rules of length at most 3. We further prove that such P system allowing division rules for non-elementary membranes can efficiently solve the PSPACE-complete problem, QSAT in a uniform way.application/pdf8engAttribution-NonCommercial-NoDerivatives 4.0 Internacionalhttp://creativecommons.org/licenses/by-nc-nd/4.0/Cell-like P systemSymport/antiport rulesMembrane divisionSubset Sum problemQSAT probleminfo:eu-repo/semantics/articleinfo:eu-repo/semantics/openAccess10.1016/j.biosystems.2015.03.00220834965