Implicit computational complexity and probabilistic classes

The thesis applies the ICC tecniques to the probabilistic polinomial complexity classes in order to get an implicit characterization of them. The main contribution lays on the implicit characterization of PP (which stands for Probabilistic Polynomial Time) class, showing a syntactical characterisation of PP and a static complexity analyser able to recognise if an imperative program computes in Probabilistic Polynomial Time. The thesis is divided in two parts. The first part focuses on solving the problem by creating a prototype of functional language (a probabilistic variation of lambda calculus with bounded recursion) that is sound and complete respect to Probabilistic Prolynomial Time. The second part, instead, reverses the problem and develops a feasible way to verify if a program, written with a prototype of imperative programming language, is running in Probabilistic polynomial time or not. This thesis would characterise itself as one of the first step for Implicit Computational Complexity over probabilistic classes. There are still open hard problem to investigate and try to solve. There are a lot of theoretical aspects strongly connected with these topics and I expect that in the future there will be wide attention to ICC and probabilistic classes.

Extending Implicit Computational Complexity and Abstract Machines to Languages with Control

The Curry-Howard isomorphism is the idea that proofs in natural deduction can be put in correspondence with lambda terms in such a way that this correspondence is preserved by normalization. The concept can be extended from Intuitionistic Logic to other systems, such as Linear Logic. One of the nice conseguences of this isomorphism is that we can reason about functional programs with formal tools which are typical of proof systems: such analysis can also include quantitative qualities of programs, such as the number of steps it takes to terminate. Another is the possiblity to describe the execution of these programs in terms of abstract machines. In 1990 Griffin proved that the correspondence can be extended to Classical Logic and control operators. That is, Classical Logic adds the possiblity to manipulate continuations. In this thesis we see how the things we described above work in this larger context.

Probabilistic Recursion Theory and Implicit Computational Complexity

In this thesis we provide a characterization of probabilistic computation in itself, from a recursion-theoretical perspective, without reducing it to deterministic computation. More specifically, we show that probabilistic computable functions, i.e., those functions which are computed by Probabilistic Turing Machines (PTM), can be characterized by a natural generalization of Kleene's partial recursive functions which includes, among initial functions, one that returns identity or successor with probability 1/2. We then prove the equi-expressivity of the obtained algebra and the class of functions computed by PTMs. In the the second part of the thesis we investigate the relations existing between our recursion-theoretical framework and sub-recursive classes, in the spirit of Implicit Computational Complexity. More precisely, endowing predicative recurrence with a random base function is proved to lead to a characterization of polynomial-time computable probabilistic functions.

Assessment of a best practise approach for the attribution and authentication of paintings

The ever-growing interest in scientific techniques, able to characterise the materials and rediscover the steps behind the execution of a painting, makes them widely accepted in its investigation. This research discusses issues emerging from attribution and authentication studies and proposes best practise for the characterisation of materials and techniques, favouring the contextualisation of the results in an integrated approach; the work aims to systematically classify paintings in categories that aid the examination of objects. A first grouping of paintings is based on the information initially available on them, identifying four categories. A focus of this study is the examination of case studies, spanning from the 16th to the 20th century, to evaluate and validate different protocols associated to each category, to show problems arising from paintings and explain advantages and limits of the approach. The research methodology incorporates a combined set of scientific techniques (non-invasive, such as technical imaging and XRF, micro-invasive, such as optical microscopy, SEM-EDS, FTIR, Raman microscopy and in one case radiocarbon dating) to answer the questions and, if necessary for the classification, exhaustively characterise the materials of the paintings, as the creation and contribution of shared technical databases related to various artists and their evolution over time is an objective tool that benefits this kind of study. The reliability of a close collaboration among different professionals is an essential aspect of this research to comprehensively study a painting, as the integration of stylistic, documentary and provenance studies corroborates the scientific findings and helps in the successful contextualisation of the results and the reconstruction of the history of the object.