Depth-two P systems can simulate Turing machines with \textbf{NP} oracles

DOI10.1016/J.TCS.2021.11.010OpenAlexW3215479332MaRDI QIDQ2077403

Alberto Leporati, Claudio Zandron, Luca Manzoni, Giancarlo Mauri

Publication date: 21 February 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2021.11.010

zbMATH Keywords

P systemsactive membranes\textbf{NP} oracles

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Membrane creation and symport/antiport rules solving QSAT

Cites Work

• The computational power of membrane systems under tight uniformity conditions
• Membrane computing and complexity theory: A characterization of PSPACE
• Tissue P systems.
• Computing with membranes
• The counting power of P systems with antimatter
• A guide to membrane computing.
• Membrane computing. An introduction.
• Simulating counting oracles with cooperation
• Minimal cooperation as a way to achieve the efficiency in cell-like membrane systems
• P systems attacking hard problems beyond NP: a survey
• Monodirectional P systems
• Characterising the complexity of tissue P systems with fission rules
• A path to computational efficiency through membrane computing
• Membrane Division, Oracles, and the Counting Hierarchy
• Polarizationless P Systems with Active Membranes: Computational Complexity Aspects
• Simulating Elementary Active Membranes
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Depth-two P systems can simulate Turing machines with \textbf{NP} oracles