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

Opened Access Deterministic Solutions to QSAT and Q3SAT by Spiking Neural P Systems with Pre-Computed Resources
Estadísticas
Icon
Exportar a
Autor: Ishdorj, Tseren-Onolt
Leporati, Alberto
Pan, Linqiang
Zeng, Xiangxiang
Zhang, Xingyi
Fecha: 2009
Publicado en: 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
Tipo de documento: Ponencia
Resumen: 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.
Tamaño: 618.6Kb
Formato: PDF

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

Mostrar el registro completo del ítem


Esta obra está bajo una Licencia Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 Internacional

Este registro aparece en las siguientes colecciones