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

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...

Figure