Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources

被引：124

作者：

Ishdorj, Tseren-Onolt ^{[2
]}

Leporati, Alberto ^{[3
]}

Pan, Linqiang ^{[1
]}

Zeng, Xiangxiang ^{[1
]}

Zhang, Xingyi ^{[1
]}

机构：

[1] Huazhong Univ Sci & Technol, Dept Control Sci & Engn, Key Lab Image Proc & Intelligent Control, Wuhan 430074, Peoples R China

[2] Abo Akad Univ, Dept Informat Technol, Computat Biomodelling Lab, FIN-20520 Turku, Finland

[3] Univ Milano Bicocca, Dipartimento Informat Sistemist & Comunicaz, I-20126 Milan, Italy

来源：

THEORETICAL COMPUTER SCIENCE | 2010年 / 411卷 / 25期

基金：

中国国家自然科学基金; 芬兰科学院;

关键词：

Spiking neural P systems; PSPACE-complete problems; QSAT; Q3SAT;

D O I：

10.1016/j.tcs.2010.01.019

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：2345 / 2358

页数：14

共 17 条

[1]

[Anonymous], 208 TUCS

[2]

BALCAZAR JL, 1988, STRUCTURAL COMPLEXIT, V1

[3]

CHEN H, 2006, 4 BRAINSTORMING WEEK, V3, P195

[4]

Chen HM, 2007, FUND INFORM, V75, P141