5 July 2010
Today we submitted the final version of our paper P systems with elementary active membranes: Beyond NP and coNP, which has been accepted for the Eleventh International Conference on Membrane Computing, taking place on 24–27 August.
The venue of CMC11 is Friedrich-Schiller-Universität in Jena, Germany. This university has some slightly notable alumni, such as Rudolf Carnap, Gottlob Frege, Gottfried “Calculemus” Leibniz, Karl Marx, and Arthur Schopenhauer among others; the teaching staff was marginally interesting too, including modest names such as Gottlieb Fichte, Georg Wilhelm Friedrich Hegel, Friedrich Schelling, and Friedrich Schiller himself. In short, rest assured that I certainly won’t be going around hunting for busts or statues of these guys, and that I won’t get someone to take pictures of me beside them to post on this blog.
Anyway, in our paper we solve a PP-complete problem via P systems with active membranes, using only division for elementary membranes (that is, membranes that don’t contain other membranes). The problem is a variant of Majority-SAT.
P systems with elementary active membranes are known for their ability to generate exponentially many membranes in linear time by using membrane division. These membranes can then explore, in a parallel way, the whole space of candidate solutions of an NP-complete problem, thus solving it in polynomial time.
In the paper we extend this algorithm (which is pretty standard in our literature) by checking whether the number of membranes finding a satisfying assignment exceeds a certain threshold, instead of just checking whether there is at least one. Lo and behold, not only we can solve NP-complete problems in polynomial time, but also PP-complete ones.