title: Efficient solutions to hard computational problems by P systems with symport/antiport rules and membrane division.
abstract: P 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.
authors: Key Laboratory of Image Information Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China; Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain. Electronic address: boshengsong@163.com.
authors: Bosheng
authors: B
authors: Song
authors: Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain. Electronic address: marper@us.es.
authors: Mario J
authors: MJ
authors: Pérez-Jiménez
authors: Key Laboratory of Image Information Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China. Electronic address: lqpan@mail.hust.edu.cn.
authors: Linqiang
authors: L
authors: Pan
mesh_terms: D002462:Cell Membrane; D003198:Computer Simulation; D008954:Models, Biological
keywords: Cell-like P system; Membrane division; QSAT problem; Subset Sum problem; Symport/Antiport rule