Computational efficiency of dissolution rules in membrane systems

TitleComputational efficiency of dissolution rules in membrane systems
Publication TypeJournal Papers
Year of Publication2006
AuthorsGutiérrez-Naranjo, M. A., Pérez-Jiménez M. J., Riscos-Núñez A., & Romero-Campero F. J.
Journal TitleInternational Journal of Computer Mathematics
Place PublishedLondres
Volume83
Pages593-611
Abstract

Trading (in polynomial time) space for time in the framework of membrane systems is not sufficient to efficiently solve computationally hard problems. On the one hand, an exponential number of objects generated in polynomial time is not sufficient to solve NP-complete problems in polynomial time. On the other hand, when an exponential number of membranes is created and used as workspace, the situation is very different. Two operations in P systems (membrane division and membrane creation) capable of constructing an exponential number of membranes in linear time are studied in this paper. NP-complete problems can be solved in polynomial time using P systems with active membranes and with polarizations, but when electrical charges are not used, then dissolution rules turn out to be very important. We show that in the framework of P systems with active membranes but without polarizations and in the framework of P systems with membrane creation, dissolution rules play a crucial role from the computational efficiency point of view.

KeywordsComputational efficiency; Dissolution rules; Membrane systems
URLhttp://www.informaworld.com/smpp/content~content=a769606660~db=all~order=page
Issue7
DOI10.1080/00207160601065413
AttachmentSize
Computational Efficiency.pdf208.62 KB