Further remark on P systems with active membranes and two polarizations

P systems (or membrane systems) are a class of distributed parallel Computing devices of a biochemical type. In this paper, some restrictions on the general form of the developing rules are considered, under which it is still possible to solve NP-complete problems. We present an algorithm for deterministically deciding SAT in linear time by P systems with active membranes using two polarizations and rules of restricted versions of types (a). (c). (e). The result obtained in this paper answered an open problem proposed by Alhazov and Freund in the aspect of computing efficiency. (C) 2006 Elsevier Inc. All rights reserved.