A linear time solution for QSAT with membrane creation

Thu, 11/29/2007 - 13:44 — ana

Title	A linear time solution for QSAT with membrane creation
Publication Type	Journal Papers
Year of Publication	2006
Authors	Gutiérrez-Naranjo, M. A., Pérez-Jiménez M. J., & Romero-Campero F. J.
Journal Title	Lecture Notes in Computer Science
ISBN Number	978-3-540-30948-2
Publisher	Springer
Place Published	Amsterdam, The Netherlands
Volume	3850
Pages	241-252
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.
URL	http://www.springerlink.com/content/f581751081374261/?p=b39de80f23a244a2b3abbcfb36e1340a&pi=16
ISSN Number	0302-9743
DOI	10.1007/11603047