Solving a Special Case of the P Conjecture Using Dependency Graphs with Dissolution
作者： Alberto Leporati , Luca Manzoni , Giancarlo Mauri , Antonio E. Porreca , Claudio Zandron
DOI: 10.1007/978-3-319-73359-3_13
关键词:
摘要: We solve affirmatively a new special case of the P conjecture by Gh. Păun, which states that systems with active membranes without charges and non-elementary membrane division cannot \(\mathbf {NP}\)-complete problems in polynomial time. The variant we consider is monodirectional, i.e., send-in communication rules, shallow, structures consisting only one level besides external membrane, deterministic, rather than more generally confluent. describe polynomial-time Turing machine simulation this systems, exploiting generalised version dependency graphs for which, unlike original introduced Cordon-Franco et al., also takes dissolution into account.
springer.com
units.it参考文章(14)
Artiom Alhazov, Mario J. Pérez-Jiménez, Uniform solution of QSAT using polarizationless active membranes machines computations and universality. pp. 122- 133 ,(2007) , 10.1007/978-3-540-74593-8_11
Alberto Leporati, Luca Manzoni, Giancarlo Mauri, Antonio E. Porreca, Claudio Zandron, Simulating Elementary Active Membranes Membrane Computing. ,vol. 8961, pp. 284- 299 ,(2014) , 10.1007/978-3-319-14370-5_18
Miguel A. Gutiérrez–Naranjo, Mario J. Pérez–Jiménez, Agustín Riscos–Núñez, Francisco J. Romero–Campero, On the Power of Dissolution in P Systems with Active Membranes Membrane Computing. pp. 224- 240 ,(2006) , 10.1007/11603047_16
Miguel A. Gutiérrez-Naranjo, Mario J. Pérez-Jiménez, Agustín Riscos-Núñez, Francisco J. Romero-Campero, P Systems with Active Membranes, Without Polarizations and Without Dissolution: A Characterization of P Lecture Notes in Computer Science. pp. 105- 116 ,(2005) , 10.1007/11560319_11
Artiom Alhazov, Rudolf Freund, On the Efficiency of P Systems with Active Membranes and Two Polarizations Membrane Computing. pp. 146- 160 ,(2005) , 10.1007/978-3-540-31837-8_8
Damien Woods, Niall Murphy, Mario J. Pérez-Jiménez, Agustín Riscos-Núñez, Membrane Dissolution and Division in P international conference on unconventional computation. ,vol. 5715, pp. 262- 276 ,(2009) , 10.1007/978-3-642-03745-0_28
Mario J. Péerez Jiménez, Álvaro Romero Jiménez, Fernando Sancho Caparrini, Complexity classes in models of cellular computing with membranes Natural Computing. ,vol. 2, pp. 265- 285 ,(2003) , 10.1023/A:1025449224520
Andrés Cordón-Franco, Miguel A. Gutiérrez-Naranjo, Mario J. Pérez-Jiménez, Agustín Riscos-Núñez, Exploring Computation Trees Associated with P Systems Membrane Computing. pp. 278- 286 ,(2005) , 10.1007/978-3-540-31837-8_16
Niall Murphy, Damien Woods, The computational power of membrane systems under tight uniformity conditions Natural Computing. ,vol. 10, pp. 613- 632 ,(2011) , 10.1007/S11047-010-9244-7
Petr Sosík, Alfonso Rodríguez-Patón, Membrane computing and complexity theory: A characterization of PSPACE Journal of Computer and System Sciences. ,vol. 73, pp. 137- 152 ,(2007) , 10.1016/J.JCSS.2006.10.001