Simulating counting oracles with cooperation
- PDF / 1,243,007 Bytes
- 8 Pages / 595.276 x 790.866 pts Page_size
- 19 Downloads / 251 Views
REGULAR PAPER
Simulating counting oracles with cooperation Alberto Leporati1 · Luca Manzoni2 · Giancarlo Mauri1 · Antonio E. Porreca3 · Claudio Zandron1 Received: 10 June 2020 / Accepted: 30 September 2020 / Published online: 2 December 2020 © Springer Nature Singapore Pte Ltd. 2020
Abstract Many variants of P systems with active membranes are able to solve traditionally intractable problems. Sometimes they also characterize well known complexity classes, depending upon the computational features they use. In this paper we continue the investigation of the importance of (minimal) cooperative rules to increase the computational power of P systems. In particular, we prove that monodirectional shallow chargeless P systems with active membranes and minimal cooperation working in polynomial time precisely characterise 𝐏#𝐏 , the complexity class of problems solved in polynomial time by ∥ deterministic Turing machines with a polynomial number of parallel queries to an oracle for a counting problem. Keywords P systems with active membranes · Counting oracles · Minimal cooperation · Monodirectional P systems · Chargeless P systems
1 Introduction Membrane systems, also called P systems, have been introduced by Păun in 1998 as a framework for defining parallel models of computation inspired from the functioning of living cells. For an introduction to the subject we refer the reader to [16, 18], whereas the latest information and an extensive bibliography can be found in the P systems webpage [21]; a useful reference is also The Oxford Handbook of Membrane Computing [17], that contains a comprehensive presentation of the state of knowledge in 2010.
* Alberto Leporati [email protected] Luca Manzoni [email protected] Giancarlo Mauri [email protected] Claudio Zandron [email protected] 1
Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Viale Sarca 336, 20126 Milan, Italy
2
Dipartimento di Matematica e Geoscienze, Università degli Studi di Trieste, Via Alfonso Valerio 12/a, 24127 Trieste, Italy
3
Université Publique, Marseille, France
Membrane computing is currently an active field of research, where three types of models have been extensively studied: cell-like P systems [14], based on the hierarchical structure of the membranes within a living cell; tissue-like P systems [9], based on the intercommunication between the cells in a biological tissue; and spiking neural P systems [2] inspired by the electrical impulses that neurons emit as information. The computing elements of P systems are usually arranged as the nodes of tree-like or graph-like architectures, and perform their computations by rewriting multisets of objects through transformation rules taken from appropriate formal grammars. Since their birth, P systems have stimulated a relevant number of investigations both on the theoretical side—dealing with computability and their computing power and efficiency in solving computationally difficult problems—and from the point o
Data Loading...
