Time and Space Complexity of P Systems — And Why They Matter

Computational complexity theory allows one to investigate the amount of resources (usually, time and/or space) which are needed to solve a given computational problem. Indeed, since the appearance of P systems several computational complexity techniques have been applied to study their computational power and efficiency. In this paper, starting from some results which have been obtained in the last few years by the group of Membrane Computing at the University of Milan-Bicocca (also known as the “Milano Team”), sometimes in collaboration with colleagues from the Membrane Computing community, I will make some observations on what is the relevance (in my opinion) of time and space complexity theory for P systems. Speaking about the results, I will focus in particular on the ideas lying behind them, without delving into technical details. I will also comment on the importance of these results for applications, such as modelling complex systems and implementing decentralized applications. I will finally conclude with some (somewhat provocative) connections with other Computer Science subjects, related with Cryptography, Computer and Network Security, and Decentralized Applications.