Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources
作者： Tseren-Onolt Ishdorj , Alberto Leporati , Linqiang Pan , Xiangxiang Zeng , Xingyi Zhang
DOI: 10.1016/J.TCS.2010.01.019
关键词:
摘要: In this paper we continue previous studies on the computational efficiency of spiking neural P systems, under assumption that some pre-computed resources exponential size are given in advance. Specifically, give a deterministic solution for each two well known PSPACE-complete problems: QSAT and Q3SAT. case QSAT, answer to any instance problem is computed time which linear with respect both number n Boolean variables m clauses compose instance. As Q3SAT, at most cubic variables.
core.ac.uk
us.es
elsevier.com
sci-hub.se 参考文章(19)
M. p. h. R. Gary, Johnson: Computers and Intractability-A Guide to the Theory of NP-Completeness ,(1979)
Haiming Chen, Mihai Ionescu, Tseren-Onolt Ishdorj, Andrei Păun, Gheorghe Păun, Mario J. Pérez-Jiménez, Spiking neural P systems with extended rules: universality and languages Natural Computing. ,vol. 7, pp. 147- 166 ,(2008) , 10.1007/S11047-006-9024-6
Gheorghe Păun, Rudolf Freund, Mihai Ionescu, Mario J. Pérez-Jiménez, Haiming Chen, On String Languages Generated by Spiking Neural P Systems Fundamenta Informaticae. ,vol. 75, pp. 141- 162 ,(2007)
Gheorghe Păun, Computing with Membranes Journal of Computer and System Sciences. ,vol. 61, pp. 108- 143 ,(2000) , 10.1006/JCSS.1999.1693
Claudio Zandron, Alberto Leporati, Giancarlo Mauri, Claudio Ferretti, On the Computational Power of Spiking Neural P Systems International Journal of Unconventional Computing. ,vol. 5, pp. 459- 473 ,(2009)
A. Salomaa, Formal Languages ,(1973)
Mihai Ionescu, Haiming Chen, Tseren-Onolt Isdorj, On the Efficiency of Spiking Neural P Systems ICEIC : International Conference on Electronics, Informations and Communications. pp. 49- 51 ,(2006)
Michael Randolph Garey, David S. Johnson, A guide to the theory of np-completeness ,(1978)
Mihai Ionescu, Cheng Haiming, Tseren-Onolt Ishdorj, On the Efficiency of Spiking Neural P Systems Fourth Brainstormming Week on Membrane Computing, Vol. 1, 2006, ISBN 8461105206, págs. 195-206. pp. 195- 206 ,(2006)
Alberto Leporati, Claudio Zandron, Claudio Ferretti, Giancarlo Mauri, Solving numerical NP-complete problems with spiking neural P systems international conference on membrane computing. ,vol. 4860, pp. 336- 352 ,(2007) , 10.1007/978-3-540-77312-2_21