Published January 21, 2016
| Version v1
Publication
A Characterization of PSPACE with Antimatter and Membrane Creation
Description
The use of negative information provides a new tool for exploring the limits
of P systems as computational devices. In this paper we prove that the combination of
antimatter and annihilation rules (based on the annihilation of physical particles and
antiparticles) and membrane creation (based on autopoiesis) provides a P system model
able to solve PSPACE-complete problems. Namely, we provide a uniform family of
P system in such P system model which solves the satis ability problem for quanti ed
Boolean formulas (QSAT). In the second part of the paper, we prove that all the decision
problems which can be solved with this P system model belong to the complexity class
PSPACE, so this P system model characterises PSPACE.
Abstract
Ministerio de Economía y Competitividad TIN2012-37434Additional details
Identifiers
- URL
- https://idus.us.es/handle/11441/33046
- URN
- urn:oai:idus.us.es:11441/33046