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.