Font size: Αα Αα Αα hide gadgets
You are here: Defenses » Σεπτέμβριος 2016 » Αγγελική Χαλκή
download defense details: { pdf }

MSc thesis defense presentation

Αγγελική Χαλκή defends her MSc thesis.

Date: Δευτέρα, 12 Σεπ 2016
Ώρα: 17:00
Location: Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, ΕΜΠ (παλαιά κτήρια), 1.1.31
Thesis title: Counting below #P: Classes, problems and Descriptive Complexity

Thesis abstract

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.


Web standards: XHTML1.0, CSS3.
© 1996 – 2018 MPLA: Graduate program in Logic, Algorithms and Computation.
Contact the webmaster.