Repositorio de producción científica de la Universidad de Sevilla

A Linear Solution for QSAT with Membrane Creation


Advanced Search
Opened Access A Linear Solution for QSAT with Membrane Creation

Show item statistics
Export to
Author: Gutiérrez Naranjo, Miguel Ángel
Pérez Jiménez, Mario de Jesús
Romero Campero, Francisco José
Department: Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial
Date: 2006
Published in: Membrane Computing 6th International Workshop, WMC 2005, Vienna, Austria, July 18-21, 2005, Revised Selected and Invited Papers. Lecture Notes in Computer Science Volume 3850
ISBN/ISSN: 978-3-540-30948-2
Document type: Chapter of Book
Abstract: The usefulness of P systems with membrane creation for solving NP problems has been previously proved (see [2, 3]), but, up to now, it was an open problem whether such P systems were able to solve PSPACE-complete problems in polynomial time. In this paper we give an answer to this question by presenting a uniform family of P system with membrane creation which solves the QSAT-problem in linear time.
Size: 494.3Kb
Format: PDF


DOI: 10.1007/11603047_17

See editor´s version

This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)