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
Place PublishedAmsterdam, The Netherlands

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.

ISSN Number0302-9743