Repositorio de producción científica de la Universidad de Sevilla

Deterministic Solutions to QSAT and Q3SAT by Spiking Neural P Systems with Pre-Computed Resources

 

Advanced Search
 
Opened Access Deterministic Solutions to QSAT and Q3SAT by Spiking Neural P Systems with Pre-Computed Resources
Cites
Show item statistics
Icon
Export to
Author: Ishdorj, Tseren-Onolt
Leporati, Alberto
Pan, Linqiang
Zeng, Xiangxiang
Zhang, Xingyi
Date: 2009
Published in: Proceedings of the Seventh Brainstorming Week on Membrane Computing, vol.II, 1-27. Sevilla, E.T.S. de Ingeniería Informática, 2-6 de Febrero, 2009
ISBN/ISSN: 9788461328369
Document type: Presentation
Abstract: In this paper we continue previous studies on the computational effciency 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.
Size: 618.6Kb
Format: PDF

URI: http://hdl.handle.net/11441/38898

This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)