Showing 2023Show all
2 papers · 1 filter
cs.CC2023
On the power of counting the total number of computation paths of NPTMs
Eleni Bakali, Aggeliki Chalki, Sotiris Kanellopoulos +2
In this paper, we define and study variants of several complexity classes of decision problems that are defined via some criteria on the number of accepting paths of an NPTM. In th…
cs.LO2023
Counting Computations with Formulae: Logical Characterisations of Counting Complexity Classes
Antonis Achilleos, Aggeliki Chalki
We present quantitative logics with two-step semantics based on the framework of quantitative logics introduced by Arenas et al. (2020) and the two-step semantics defined in the co…