Uniform Solution to QSAT by P Systems with Proteins[J]. Chinese Journal of Electronics, 2012, 21(4): 667-672.
Citation: Uniform Solution to QSAT by P Systems with Proteins[J]. Chinese Journal of Electronics, 2012, 21(4): 667-672.

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
  • 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.
  • loading
  • 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.
  • 加载中


    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (447) PDF downloads(1250) Cited by()
    Proportional views


    DownLoad:  Full-Size Img  PowerPoint