|
|||||
|
|
Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources |
|
| Authors: | Tseren-Onolt Ishdorj Xiangxiang Zeng |
| Affiliation: | a Key Laboratory of Image Processing and Intelligent Control, Department of Control Science and Engineering, Huazhong University of Science and Technology, 430074 Wuhan, China b Computational Biomodelling Laboratory, Department of Information Technologies, A?bo Akademi University, Turku 20520, Finland c Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Viale Sarca 336/14, 20126 Milano, Italy |
| 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. |
| Keywords: | Spiking neural P systems PSPACE-complete problems" target="_blank">PSPACE-complete problems QSAT Q3SAT |
| 本文献已被 ScienceDirect 等数据库收录！ | |