Uniform Solution to QSAT by P Systems with Proteins

Article Contents

Article Navigation > Chinese Journal of Electronics > 2012 > 21(4): 667-672

“Uniform Solution to QSAT by P Systems with Proteins,” Chinese Journal of Electronics, vol. 21, no. 4, pp. 667-672, 2012,

Citation:

“Uniform Solution to QSAT by P Systems with Proteins,” Chinese Journal of Electronics, vol. 21, no. 4, pp. 667-672, 2012,

“Uniform Solution to QSAT by P Systems with Proteins,” Chinese Journal of Electronics, vol. 21, no. 4, pp. 667-672, 2012,

Citation:

“Uniform Solution to QSAT by P Systems with Proteins,” Chinese Journal of Electronics, vol. 21, no. 4, pp. 667-672, 2012,

PDF( 210 KB)

Uniform Solution to QSAT by P Systems with Proteins

Funds: null

Received Date: 2011-08-01
Rev Recd Date: 2011-09-01
Publish Date: 2012-10-25

Abstract

Abstract

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 satisfiability 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 membranes can solve in polynomial time exactly the class of problems PSPACE. In this work, we present a uniform solution 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.

FullText(HTML)

References(19)

References

G. P?un, “Computing with membranes”, Journal of Computerand System Sciences, Vol.61, No.1, pp.108-143, 2000.

L. Pan, G. P?un, “Spiking neural P systems with anti-spikes”,International Journal of Computers, Communications & Control,Vol.4, No.3, pp.273-282, 2009.

L. Pan, G. P?un, “Spiking neural P systems: an improved normalform”, Theoretical Computer Science, Vol.411, pp.906-918,2010.

J. Wang, H.J. Hoogeboom, L. Pan, Gh. P?un, M.J. Pérez-Jiménez, “Spiking neural P systems with weights”, Neural Computation,Vol.22, No.10, pp.2615-2646, 2010.

L. Pan, X. Zeng, X. Zhang, “Time-free spiking neural P systems”,Neural Computation, Vol.23, No.5, pp.1320-1342, 2011.

T.O. Ishdorj, A. Leporati, L. Pan, X. Zeng, X. Zhang, “Deterministicsolutions to QSAT and Q3SAT by spiking neural Psystems with pre-computed resources”, Theoretical ComputerScience, Vol.411, pp.2345-2358, 2010.

X. Zhang, S. Wang, Y. Niu, L. Pan, “Tissue P systems with cellseparation: attacking the partition problem”, Science ChinaInformation Sciences, Vol.54, No.2, pp.293-304, 2011.

Y. Niu, L. Pan, M.J. Pérez-Jiménez, M.R. Font, “A tissue P systemsbased uniform solution to tripartite matching problem”,Fundamenta Informaticae, Vol.109, pp.179-188, 2011.

L. Pan, M.J. Pérez-Jiménez, “Computational complexity oftissue-like P systems”, Journal of Complexity, Vol.26, No.3,pp.296-315, 2010.

A. P?un, B. Popa, “P systems with proteins on membranesand membrane division”, Lecture Notes in Computer Science,Vol.4036, pp.292-303, 2006.

L. Cardelli, “Brane calculi”, Lecture Notes in Computer Science,Vol.3082, pp.257-280, 2005.

L. Cardelli, G. P?un, “An universality result for a (mem) branecalculus based on mate/drip operations”, International Journalof Foundations of Computer Science, Vol.17, No.1, pp.49-68,2006.

S.N. Krishna, “Universality results for P systems based onBrane Calculi operations”, Theoretical Computer Science,Vol.371, No.1, pp.83-105, 2007.

G. P?un, “P Systems with active membranes: attacking NPcompleteproblems”, Journal of Automata, Languages andCombinatorics, Vol.6, No.1, pp.75-90, 2001.

C. Zandron, A. Leporati, C. Ferretti, G. Mauri, “On the computationalefficiency of polarizationless recognizer P systemswith strong division and dissolution”, Fundamenta Informaticae,Vol.87, No.1, pp.79-91, 2008.

A. P?un, B. Popa, “P systems with proteins on membranes”,Fundamenta Informaticae, Vol.72, No.4, pp.467-483, 2006.

P. Sosík, A. P?un, A. Rodríguez-Patón, David Pérez, “Onthe power of computing with proteins on membranes”, LectureNotes in Computer Science, Vol.5957, pp.448-460, 2010.

G. P?un, Membrane Computing-An Introduction, Springer-Verlag, Berlin, pp.51-125, 2002.

M.J. Pérez-Jiménez, A. Romero-Jiménez, F. Sancho-Caparrini,“A polynomial complexity class in P systems using membranedivision”, Journal of Automation, Languages and Combinatorics,Vol.11, No.4, pp.423-434, 2006.

Relative Articles

Supplements(0)

Cited By

Proportional views