Uniform Solution to QSAT by P Systems with Proteins  

作　　者：LU Chun SHI Xiaolong 

机构地区：[1]Key Laboratory of Image Processing and Intelligent Control, Department of Control Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China

出　　处：《Chinese Journal of Electronics》2012年第4期667-672,共6页电子学报（英文版）

基　　金：This work is supported by the National Natural Science Foundation of China （No.61033003, No.60971085）, the Opening Fund of Key Laboratory of Image Processing and Intelligent Control, Ministry of Education （No.200905）.

摘　　要：P systems are distributed parallel computing models in the area of membrane computing, which are inspired by the structure and the functioning of living cells, as well as the organization of cells in tissues, organs, and other higher order structures. P systems with proteins on membranes are a class of P systems, which have proved to be very efficient computing devices. Specifically, it was known that the Quantified satisflability problem （QSAT） of a Boolean formula can be solved by a semi-uniform family of P systems with proteins on membranes and with membrane division. However, it remains open whether a uniform families of P systems with proteins on mem- branes can solve in polynomial time exactly the class of problems PSPACE. In this work, we present a uniform so- lution to QSAT problem by P systems with proteins on membranes in a linear time with respect to both the number n of Boolean variables and the number m of clauses of the instance, which answers the above open problem.

关 键 词：Membrane computing Membrane protein PSPACE-complete problem Quantified satisflability problem （QSAT problem） Uniform solution. 

分 类 号：Q510.1[生物学—生物化学] TB484.9[一般工业技术—包装工程]