Characterizations and approximability of hard counting classes below #P

Eleni Bakali, Aggeliki Chalki, Aris Pagourtzis

An important objective of research in counting complexity is to understand which counting problems are approximable. In this quest, the complexity class TotP, a hard subclass of #P…