GUO Ping, ZHU Jian, CHEN Haizhu, YANG Ruilong. A Linear-Time Solution for All-SAT Problem Based on P System[J]. Chinese Journal of Electronics, 2018, 27(2): 367-373. doi: 10.1049/cje.2018.01.008
Citation: GUO Ping, ZHU Jian, CHEN Haizhu, YANG Ruilong. A Linear-Time Solution for All-SAT Problem Based on P System[J]. Chinese Journal of Electronics, 2018, 27(2): 367-373. doi: 10.1049/cje.2018.01.008

A Linear-Time Solution for All-SAT Problem Based on P System

doi: 10.1049/cje.2018.01.008
Funds:  This work is supported by the Fundamental Research Funds for the Central Universities (No.CDJZR121800002), Chongqing Natural Science Foundation (No.cstc2013jcyjA40046), and the National Natural Science Foundation of China (No.61201347).
  • Received Date: 2016-04-11
  • Rev Recd Date: 2016-06-03
  • Publish Date: 2018-03-10
  • P system is a new kind of distributed parallel computing model, and its many variants are used to solve NP problems. All-SAT problem is a well-known NPhard problem and it has been widely applied in the fields of project selection problem, capital budgeting problem and so on. In this paper, we present a family of P systems to solve All-SAT problem in a linear time based on membrane division and give an instance to illustrate the feasibility and effectiveness of our designed P systems.
  • loading
  • S.A. Cook, "The complexity of theorem-proving procedure", Proc. of the Third Annual ACM Symposium on Theory of Computing. Shaker Heights, Ohio, USA, pp.151-158, 1971.
    M. Davis and H. Putnam, "A computing procedure for quantification theory", Journal of the ACM, Vol.7, No.3, pp.201-215, 1960.
    E. Koutsoupias and C.H. Papadimitriou, "On the greedy algorithm for satisfiability", Information Processing Letters, Vol.43, No.1, pp.53-55, 1992.
    S.A. Cook, O. Grumberg, A. Schuster, et al., "Memeory efficient all-solutions SAT solver and its application for reachability anlysis", Proc. of Fifth International Conference on Formal Methods in Computer-Aided Design, Austin, Texas, USA, pp.275-289, 2004,
    E. Birnbaum and E.L. Lozinskii, "The good old davis-putnam procedure helps counting models", Journal of Artificial Intelligence Research, Vol.10, No.1, pp.457-477, 1999.
    R.J. Bayardo and J.D. Pehoushek, "Counting models using connected components", Proc. of Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, pp.157-162, 2000.
    Gh. Pǎun, "A quick overview of membrane computing with some details about spiking neural P systems", Frontiers of Computer Science, Vol.1, No.1, pp.37-49, 2007.
    X.Y. Zhang, X.X. Zeng, B. Luo, et al., "A uniform solution to the independent set problem through tissue P systems with cell separation", Frontiers of Computer Science, Vol.7, No.3, pp.350-358, 2013.
    A. Gupta, Z. Yang, P. Ashar, et al., "SAT-based image computation with application in reachability analysis", Formal Methods in Computer-Aided Design, Springer Berlin Heidelberg, pp.391-408, 2000.
    G. Ciobanu, Gh. Pǎun and M.J. Pérez-Jiménez, Applications of Membrane Computing, Springer, pp.315-346, 2006.
    K. Ishii, A. Fujiwara and H. Tagawa, "Asynchronous P systems for SAT and Hamiltonian cycle problem", Proc. of World Congress on Nature and Biologically Inspired Computing, pp.513-519, 2010.
    Z. Gazdag and G. Kolonits, "A new approach for solving SAT by P systems with active membranes ", Proc. of the Thirteenth International Conference on Membrane Computing, Budapest, Hungary, pp.195-207, 2012.
    L.Q. Pan and A. Alhazov, "Solving HPP and SAT by P systems with active membranes and separation rules", Acta Informatica, Vol.43, No.2, pp.131-145, 2006.
    H. Tagawa and A.Fujiwara, "Solving SAT and Hamiltonian cycle problem using asynchronous P systems", IEICE Transactions on Information and Systems, Vol.95, No.3, pp.746-754, 2012.
    M.A. Gutiérrez-Naranjo, M.J. Pérez-Jiménez and F.J. RomeroCampero, "A uniform solution to SAT using membrane creation", Theoretical Computer Science, Vol.371, No.1, pp.54-61, 2007.
    P. Guo, J.F. Ji and H.Z. Chen, "Solving All-SAT problems by P systems", Chinese Journal of Electronics, Vol.24, No.4, pp.744-749, 2015.
    X. Zhang, L. Pan and A. Paun, "On universality of axon P systems", IEEE Transactions on Neural Networks and Learning Systems, Vol.26, No.11, pp.2816-2829, 2015.
    X. Liu, Z. Li, J Liu, et al., "Implementation of arithmetic operations with time-free spiking neural P systems", IEEE Transactions on NanoBioscience, Vol.14, No.6, pp.617-624, 2015.
    T. Song, Q. Zou, X. Liu, et al., "Asynchronous spiking neural P Systems with rules on synapses", NeuroComputing, Vol.151, No.1, pp.1439-1445, 2015.
    T. Song and L. Pan, "Spiking neural P systems with rules on synapses working in maximum spikes consumption strategy", IEEE Transactions on NanoBioscience, Vol.14, No.1, pp.37-43, 2015
    G. Pǎun, Membrane Computing:An Introduction, SpringerVerlag, 2002.
  • 加载中

Catalog

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

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

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

    Article Metrics

    Article views (157) PDF downloads(273) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return