Probabilistic complexity classes capture the power of randomised algorithms and as such are of fundamental importance to the understanding of randomised computation. They are based on the computational model of probabilistic Turing machines, which in addition to the usual ingredients are equipped with a semi-infinite read-only tape containing a binary string called the random bits. The machine runs as an ordinary deterministic TM, consulting its random bits in a read-only fashion which steer the decisions made. The probability of an event is measured with respect to the uniform distribution on the space of all sequences of random bits. Basic complexity classes are RL (“randomised log-space”), BPP (“randomised polynomial time”), and AM (“randomised NP”).

The goal of this dissertation project is to develop a better understanding of probabilistic complexity classes from the perspective of logic and descriptive complexity theory. Descriptive complexity theory aims at characterising complexity classes by the type of logic needed to express the languages in them. Complexity classes such as NP are captured by existential second- order logic (Fagin’s theorem), whereas PSPACE corresponds to second-order logic with transitive closure. (A logical characterisation of the class P is an open problem.) These connections are important for many reasons: they allow the transfer of results between the different areas, they enable new proof methods, and provide additional evidence of the adequacy of the main complexity classes. Although for standard complexity classes several results are known, the logical description of probabilistic complexity classes is still in its infancy.

Specific questions to be considered within this dissertation project are the following: What are logical characterisations of the classes RL, BPP, and AM, possibly on ordered structures? For the complexity classes like RL and BPP, it may be hard to obtain logical characterisations on unordered structures—this is related to the important open question of a logical characterisation of P. Can we obtain logical characterisations of these complexity classes on specific classes of structures such as trees or planar graphs? What is the expressive power of the logics involved?