Asynchronous P systems with active membranes

We prove that recognising P systems with active membranes operating in asynchronous mode are able to solve in a semi-uniform way both NP-complete and PP-complete problems in linear time (in the best case) and exponential space, when using different sets of rules. Precisely, the proposed solution of k-SAT, k≥3, uses evolution and communication rules, as well as membranes creation and division of non-elementary membranes; however, it does not use neither polarisations nor membrane dissolution rules. Our solution of MAJORITY-SAT makes use of polarisations as well as evolution and communication rules, together with rules for dividing non-elementary membranes. We also prove that these systems can simulate partially blind register machines; the converse simulation holds for a constrained version of our P systems.