Deterministic Solutions to QSAT and Q3SAT by Spiking Neural P Systems with Pre-Computed Resources (bibtex)
by Ishdorj, Tseren-Onolt, Leporati, Alberto, Pan, Linqiang, Zeng, Xiangxiang and Zhan, Xingyi
Abstract:
In this paper we continue previous studies on the computational efficiency of spiking neural P systems, under the assumption that some pre-computed resources of exponential size are given in advance. Specifically, we give a deterministic solution for each of two well known PSPACE-complete problems: QSAT and Q3SAT. In the case of QSAT, the answer to any instance of the problem is computed in a time which is linear with respect to both the number -n- of Boolean variables and the number m of clauses that compose the instance. As for Q3SAT, the answer is computed in a time which is at most cubic in the number -n- of Boolean variables.
Reference:
Deterministic Solutions to QSAT and Q3SAT by Spiking Neural P Systems with Pre-Computed Resources (Ishdorj, Tseren-Onolt, Leporati, Alberto, Pan, Linqiang, Zeng, Xiangxiang and Zhan, Xingyi), In Seventh Brainstorming Week on Membrane Computing (Gh. Paun, et. al., ed.), Fenix Editora Sevilla, volume II, 2009.
Bibtex Entry:
@InProceedings{inp252,
author    = {Ishdorj, Tseren-Onolt AND Leporati, Alberto AND Pan, Linqiang AND Zeng, Xiangxiang AND Zhan, Xingyi},
title     = {Deterministic Solutions to QSAT and Q3SAT by Spiking Neural P Systems with Pre-Computed Resources},
booktitle = {Seventh Brainstorming Week on Membrane Computing},
year      = {2009},
editor    = {Gh. Paun, et. al.},
volume    = {II},
series    = {1/2009},
pages     = {1--27},
publisher = {Fenix Editora Sevilla},
abstract  = {In this paper we continue previous studies on the computational efficiency of spiking neural P systems, under the assumption that some pre-computed resources of exponential size are given in advance. Specifically, we give a deterministic solution for each of two well known PSPACE-complete problems: QSAT and Q3SAT. In the case of QSAT, the answer to any instance of the problem is computed in a time which is linear with respect to both the number -n- of Boolean variables and the number m of clauses that compose the instance. As for Q3SAT, the answer is computed in a time which is at most cubic in the number -n- of Boolean variables.},
file      = {ILPZZ2009a.pdf:pdfs/ILPZZ2009a.pdf:PDF},
}