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}, }

Powered by bibtexbrowser