Presentation
A Characterization of PSPACE with Antimatter and Membrane Creation
Author/s | Gazdag, Zsolt
Gutiérrez Naranjo, Miguel Ángel |
Department | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Publication Date | 2015 |
Deposit Date | 2016-01-21 |
Published in |
|
ISBN/ISSN | 978-84-944366-2-8 |
Abstract | 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 ... 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. |
Funding agencies | Ministerio de Economía y Competitividad (MINECO). España |
Project ID. | info:eu-repo/grantAgreement/MINECO/TIN2012-37434 |
Files | Size | Format | View | Description |
---|---|---|---|---|
159_zsolt_miguel_QSAT_7.pdf | 415.1Kb | [PDF] | View/ | |