Uniform Solution to Common Algorithmic Problem by P Systems Working in the Minimally Parallel Mode

Abstract

It is known that the Common Algorithmic Problem (CAP) has the nice property that several other NP-complete problems can be reduced to it in linear time. The decision version of this problem is known to be efficiently solved by a family of recognizer P systems with active membranes with three electrical charges working in the maximally parallel way. We here work with a variant of P systems with active membranes without polarizations and present a uniform solution to CAP in the minimally parallel mode.