On the Power of Counting the Total Number of Computation Paths of NPTMs

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 these variants, we modify the acceptance criteria so that they concern the total number of computation paths, instead of the number of accepting ones. This direction reflects the relationship between the counting classes \(\#\textsf{P}\) and \(\textsf{TotP}\) , which are the classes of functions that count the number of accepting paths and the total number of paths of NPTMs, respectively. The former is the well-studied class of counting versions of \(\textsf{NP}\) problems, introduced by Valiant (1979). The latter contains all self-reducible counting problems in \(\#\textsf{P}\) whose decision version is in \(\textsf{P}\) , among them prominent \(\#\textsf{P}\) -complete problems such as Non-negative Permanent, #PerfMatch and #DNF-Sat. We show that almost all classes introduced in this work coincide with their ‘# accepting paths’-definable counterparts, thus providing an alternative model of computation for the classes \(\mathsf {\oplus P}\) , \(\mathsf {Mod_k P}\) , \(\textsf{SPP}\) , \(\textsf{WPP}\) , \(\mathsf {C_=P}\) , and \(\textsf{PP}\) . Moreover, for each of these classes, we present a novel family of complete problems which are defined via problems that are \(\textsf{TotP}\) -complete under parsimonious reductions. This way, we show that all the aforementioned classes have complete problems that are defined via counting problems whose existence version is in \(\textsf{P}\) , in contrast to the standard way of obtaining completeness results via counting versions of \(\textsf{NP}\) -complete problems. To the best of our knowledge, prior to this work, such results were known only for \(\mathsf {\oplus P}\) and \(\mathsf {C_=P}\) . We also build upon a result by Curticapean, to exhibit yet another way to obtain complete problems for \(\textsf{WPP}\) and \(\textsf{PP}\) , namely via the difference of values of the \(\textsf{TotP}\) function #PerfMatch on pairs of graphs. Finally, for the so defined \(\textsf{WPP}\) -complete problem, we provide an exponential lower bound under the randomized Exponential Time Hypothesis, showcasing the hardness of the class.