A linear time solution for QSAT with membrane creation

TitleA linear time solution for QSAT with membrane creation
Publication TypeJournal Papers
Year of Publication2006
AuthorsGutiérrez-Naranjo, M. A., Pérez-Jiménez M. J., & Romero-Campero F. J.
Journal TitleLecture Notes in Computer Science
ISBN Number978-3-540-30948-2
PublisherSpringer
Place PublishedAmsterdam, The Netherlands
Volume3850
Pages241-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.

URLhttp://www.springerlink.com/content/f581751081374261/?p=b39de80f23a244a2b3abbcfb36e1340a&pi=16
ISSN Number0302-9743
DOI10.1007/11603047