From SAT to SAT-UNSAT using P systems with dissolution rules
Tóm tắt
Từ khóa
Tài liệu tham khảo
Alhazov, A., & Pérez-Jiménez, M. J. (2007). Uniform solution of QSAT using polarizationless active membranes. In J. Durand-Lose & M. Margenstern (Eds.), Machines, Computations, and Universality (pp. 122–133). Berlin Heidelberg, Berlin, Heidelberg: Springer.
Cai, J. Y., Gundermann, T., Hartmanis, J., Hemachandra, L. A., Sewelson, V., Wagner, K., & Wechsung, G. (1988). The boolean hierarchy i: Structural properties. SIAM Journal on Computing, 17(6), 1232–1252. https://doi.org/10.1137/0217078.
Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA (1990)
Gutiérrez-Naranjo, M. A., Pérez-Jiménez, M. J., Riscos-Núñez, A., & Romero-Campero, F. J. (2006). On the power of dissolution in p systems with active membranes. In R. Freund, G. Păun, G. Rozenberg, & A. Salomaa (Eds.), Membrane Computing (pp. 224–240). Berlin Heidelberg, Berlin, Heidelberg: Springer.
Leporati, A., Manzoni, L., Mauri, G., Porreca, A., & Zandron, C. (2020). Subroutines in P systems and closure properties of their complexity classes. Theoretical Computer Science, 805, 193–205.
Leporati, A., Manzoni, L., Mauri, G., Porreca, A., & Zandron, C. (2020). A Turing machine simulation by P systems without charges. Journal of Membrane Computing, 2, 71–79.
Macías-Ramos, L.F., Pérez-Jiménez, M.J., Riscos-Núñez, A., Valencia-Cabrera, L.: Membrane fission versus cell division: When membrane proliferation is not enough. Theoretical Computer Science 608, 57 – 65 (2015). doi: 10.1016/j.tcs.2015.06.025. http://www.sciencedirect.com/science/article/pii/S0304397515005356
Orellana-Martín, D., Valencia-Cabrera, L., Riscos-Núñez, A., & Pérez-Jiménez, M. (2019). Membrane creation in polarizationless P systems with active membranes. Fundamenta Informaticae, 171(1–4), 297–311.
Pan, L., Orellana-Martín, D., Song, B., Pérez-Jiménez, M.J.: Cell-like P systems with polarizations and minimal rules. Theoretical Computer Science 816, 1 – 18 (2020). doi: 10.1016/j.tcs.2019.10.001. http://www.sciencedirect.com/science/article/pii/S0304397519306231
Papadimitriou, C., Yannakakis, M.: The complexity of facets (and some facets of complexity). Journal of Computer and System Sciences 28(2), 244 – 259 (1984). doi: 10.1016/0022-0000(84)90068-0. http://www.sciencedirect.com/science/article/pii/0022000084900680
Papadimitriou, C.H.: Computational complexity. Addison-Wesley (1994)
Păun, G.: Computing with membranes. Journal of Computer and System Sciences 61(1), 108 – 143 (2000). doi: 10.1006/jcss.1999.1693. http://www.sciencedirect.com/science/article/pii/S0022000099916938
Păun, G. (2001). Computing with membranes: Attacking NP-complete problems. In I. Antoniou, C. S. Calude, & M. J. Dinneen (Eds.), Unconventional Models of Computation, UMC2K (pp. 94–115). London, London: Springer.
Păun, G., Rozenberg, G., & Salomaa, A. (2010). The Oxford Handbook of Membrane Computing. USA: Oxford University Press Inc.
Pérez-Jiménez, M. J., Romero-Jiménez, A., & Sancho-Caparrini, F. (2003). Complexity classes in models of cellular computing with membranes. Natural Computing, 2(3), 265–285. https://doi.org/10.1023/A:1025449224520.
Pérez Jiménez, M. J., Romero Jiménez, Á., & Sancho Caparrini, F. (2003). Decision P systems and the P $$\ne$$ NP conjecture. In G. Păun, G. Rozenberg, A. Salomaa, & C. Zandron (Eds.), Membrane Computing (pp. 388–399). Berlin Heidelberg, Berlin, Heidelberg: Springer.
Song, B., Li, K., Orellana-Martín, D., Valencia-Cabrera, L., Pérez-Jiménez, M.J.: Cell-like P systems with evolutional symport/antiport rules and membrane creation. Information and Computation p. 104542 (2020). doi: 10.1016/j.ic.2020.104542. http://www.sciencedirect.com/science/article/pii/S0890540120300304
Valencia-Cabrera, L., Orellana-Martín, D., Martínez-del Amor, M.A., Pérez-Hurtado, I., Pérez-Jiménez, M.J.: From NP-completeness to DP-completeness: A membrane computing perspective. Complexity 2020(6765097), 10 pages (2020)