2006 | OriginalPaper | Chapter
A Linear Solution for QSAT with Membrane Creation
Authors : Miguel A. Gutiérrez-Naranjo, Mario J. Pérez-Jiménez, Francisco J. Romero-Campero
Published in: Membrane Computing
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.