Journal
THEORETICAL COMPUTER SCIENCE
Volume 908, Issue -, Pages 43-55Publisher
ELSEVIER
DOI: 10.1016/j.tcs.2021.11.010
Keywords
P systems; Active membranes; NP oracles
Categories
Ask authors/readers for more resources
The paper investigates the computational power of polarizationless P systems with active membranes and the impact of membrane hierarchy depth. It shows that P systems with a membrane hierarchy depth of 2 can solve all decision problems in the complexity class P-parallel to(NP).
Among the computational features that determine the computing power of polarizationless P systems with active membranes, the depth of the membrane hierarchy is one of the least explored. It is known that this model of P systems can solve PSPACE-complete problems when no constraints are given on the depth of the membrane hierarchy, whereas the complexity class P-parallel to(#P) is characterized by monodirectional shallow P systems with minimal cooperation, whose depth is 1. No similar result is currently known for polarizationless systems without cooperation or other additional features. In this paper we show that these P systems, using a membrane hierarchy of depth 2, are able to solve at least all decision problems that are in the complexity class P-parallel to(NP) , the class of problems solved in polynomial time by deterministic Turing machines that are given the possibility to make a polynomial number of parallel queries to oracles for NP problems. (C) 2021 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available