Ponencia
Deterministic Solutions to QSAT and Q3SAT by Spiking Neural P Systems with Pre-Computed Resources
Autor/es | Ishdorj, Tseren-Onolt
Leporati, Alberto Pan, Linqiang Zeng, Xiangxiang Zhang, Xingyi |
Fecha de publicación | 2009 |
Fecha de depósito | 2016-03-22 |
Publicado en |
|
ISBN/ISSN | 9788461328369 |
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 ... 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. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
06_pspace.pdf | 618.6Kb | [PDF] | Ver/ | |