Deterministic Solutions to QSAT and Q3SAT by Spiking Neural P Systems with Pre-Computed Resources
Lists
Only you see this
Abstract
In this paper we continue previous studies on the computational effciency \nof spiking neural P systems, under the assumption that some pre-computed resources of \nexponential size are given in advance. Specifically, we give a deterministic solution for \neach of two well known PSPACE-complete problems: QSAT and Q3SAT. In the case of \nQSAT, the answer to any instance of the problem is computed in a time which is linear \nwith respect to both the number n of Boolean variables and the number m of clauses \nthat compose the instance. As for Q3SAT, the answer is computed in a time which is at \nmost cubic in the number n of Boolean variables.
BibTeX
@article{ishdorj2010deterministic,
author = {Tseren-Onolt Ishdorj and Alberto Leporati and Linqiang Pan and Xiangxiang Zeng and Xingyi Zhang},
title = {{Deterministic Solutions to QSAT and Q3SAT by Spiking Neural P Systems with Pre-Computed Resources}},
journal = {Theoretical Computer Science},
year = {2010},
doi = {10.1016/j.tcs.2010.01.019},
}Loading related content...