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.
Ishdorj, T., Leporati, A., Pan, L., Zeng, X., Zhang, X. (2010). Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre–computed resources. THEORETICAL COMPUTER SCIENCE, 411, 2345-2358 [10.1016/j.tcs.2010.01.019].
Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre–computed resources
LEPORATI, ALBERTO OTTAVIO;
2010
Abstract
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.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
