Details

Autor(en) / Beteiligte

• Ishdorj, Tseren-Onolt
• Leporati, Alberto
• Pan, Linqiang
• Zeng, Xiangxiang
• Zhang, Xingyi

Titel

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

Ist Teil von

• Theoretical computer science, 2010-05, Vol.411 (25), p.2345-2358

Ort / Verlag

Oxford: Elsevier B.V

Erscheinungsjahr

2010

Quelle

Free E-Journal (出版社公開部分のみ）

Beschreibungen/Notizen

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