Seeking computational efficiency boundaries: the Păun’s conjecture

Abstract

In 2005, Gh. Păun raised an interesting question concerning the role of electrical charges in P systems with active membranes from a complexity point of view. Specifically, he formulated a question about the computational efficiency of polarization-less P systems with dissolution rules and division rules only for elementary membranes. Several approaches have been carried out, and some partial answers have been given. This is probably the most important open problem in computational complexity theory in the framework of Membrane Computing. The study of the efficiency of membrane systems has been a very fruitful area, providing not only the above-stated partial answers, but also several frontiers of efficiency to tackle the P vs NP problem. In this work, a survey on classical and current results on complexity aspects is given, emphasizing on the frontiers of efficiency and the ingredients taken into account for each of them.