Reversible Computation and Polynomial Implicit Computational Complexity ​

Reversible Computation is a non conventional computational model in which the calculus process can go from input to output and viceversa. Reversible computation is applied in many different fields: from designing circuits in which the lower dissipation of reversible circuits would allow more integration, to modeling roll-back processes, up to bi-directional debugging. Implicit computational complexity, on the other hand, is centered on the definition of computation models that, independently of any reference to the notion of a Turing Machine (the standard model for computational complexity), characterize classes of computational complexity. This thesis will explore the possibility of defining a reversible computational model that allows the defininition only of algorithms whose time complexity is polynomial in input length. The availability of such a model may be of interest for: - the design of low-power circuits, - the expansion of knowledge about the concept of reduction among computational problems - the characterization of one-way functions - the study of the relationship between classical and Solomonoff-Kolmogorov-Chaitin computational complexity" ​