Capítulo de Libro
A Linear Solution for QSAT with Membrane Creation
Autor/es | Gutiérrez Naranjo, Miguel Ángel
Pérez Jiménez, Mario de Jesús Romero Campero, Francisco José |
Departamento | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Fecha de publicación | 2006 |
Fecha de depósito | 2017-01-31 |
Publicado en |
|
ISBN/ISSN | 978-3-540-30948-2 0302-9743 |
Resumen | 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 ... 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. |
Agencias financiadoras | Ministerio de Ciencia y Tecnología (MCYT). España |
Identificador del proyecto | TIC2002-04220-C03-01 |
Cita | Gutiérrez Naranjo, M.Á., Pérez Jiménez, M.d.J., y Romero Campero, F.J. (2006). A Linear Solution for QSAT with Membrane Creation. En 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 (pp. 241-252). Berlin: Springer. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
chp%3A10.1007%2F11603047_17.pdf | 494.3Kb | [PDF] | Ver/ | |