2012 | OriginalPaper | Chapter
P Systems with Active Membranes Operating under Minimal Parallelism
Authors : Pierluigi Frisco, Gordon Govan
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
We prove that P systems with active membranes operating under minimal parallelism are able to solve
NP-complete
and
PP-complete
problems in linear time and exponential space when using different types of rules. We also prove that these systems can simulate register machines.