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.
Leporati, A. (2019). Time and Space Complexity of P Systems — And Why They Matter. In Membrane Computing, 19th International Conference, CMC 2018 (pp.10-22).
|Citazione:||Leporati, A. (2019). Time and Space Complexity of P Systems — And Why They Matter. In Membrane Computing, 19th International Conference, CMC 2018 (pp.10-22).|
|Carattere della pubblicazione:||Scientifica|
|Presenza di un coautore afferente ad Istituzioni straniere:||No|
|Titolo:||Time and Space Complexity of P Systems — And Why They Matter|
LEPORATI, ALBERTO OTTAVIO (Primo) (Corresponding)
|Data di pubblicazione:||2019|
|Nome del convegno:||19th International Conference, CMC 2018|
|Serie:||LECTURE NOTES IN ARTIFICIAL INTELLIGENCE|
|Appare nelle tipologie:||02 - Intervento a convegno|