MSc thesis defense presentation
Aggeliki Chalki defends her MSc thesis.
|Date:||Monday, 12 Sep 2016|
|Location:||School of Electrical and Computer Engineering (old buildings), 1.1.31|
|Thesis title:||Counting below #P: Classes, problems and Descriptive Complexity|
In this thesis, we study counting classes that lie below #P. One approach, the most regular in Computational Complexity Theory, is the machine-based approach. Classes like #L, span-L and TotP, #PE are defined establishing space and time restrictions on Turing machine's computational resources.
A second approach is Descriptive Complexity's approach. It characterizes complexity classes by the type of logic needed to express the languages in them. Classes deriving from this viewpoint, like #FO, #RHΠ_1, #RΣ_2, are equivalent to #P, the class of AP-interriducible problems to #BIS, and some subclass of the problems owning an FPRAS.
A great objective of such an investigation is to gain an understanding of how “efficient counting” relates to these already defined classes. By “efficient counting” we mean counting solutions of a problem using a polynomial time algorithm or an FPRAS.
Many other interesting properties of the classes considered and their problems have been examined. For example alternative definitions of counting classes using relation-based operators, and the computational difficulty of complete problems, since complete problems capture the difficulty of the corresponding class. Moreover, in Section 3.5 we define the log-space analog of the class TotP and explore how and to what extent results can be transferred from polynomial time to logarithmic space computation.