期刊
THEORETICAL COMPUTER SCIENCE
卷 411, 期 25, 页码 2345-2358出版社
ELSEVIER
DOI: 10.1016/j.tcs.2010.01.019
关键词
Spiking neural P systems; PSPACE-complete problems; QSAT; Q3SAT
资金
- National Natural Science Foundation of China [60674106, 30870826, 60703047, 60803113]
- Program for New Century Excellent Talents in University [NCET-05-0612]
- Foundation of Ministry of Education of China [20060487014]
- Chenguang Program of Wuhan [200750731262]
- HUST-SRF [2007Z015A]
- Natural Science Foundation of Hubei Province [2008CDB113, 2008CDB180]
- Academy of Finland [122426]
- MIUR [2007]
- Academy of Finland (AKA) [122426, 122426] Funding Source: Academy of Finland (AKA)
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 in 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. (C) 2010 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据