Closure Properties and Characterizations of TotP

P. 15–24.

Ivanashev Y.

The class TotP consists of functions that count the number of all paths of a nondeterministic polynomial-time Turing machine. In this paper, we give a predicate based definition of TotP, analogous to a standard definition of #P. From a new characterization of TotP it follows that many well known #P problems belong to TotP, and TotP = #P if and only if P = NP. We show that TotP has several closure properties of #P and GapP, and also properties that are not known to hold for #P and GapP. We also prove that the closure of TotP under left composition with FP+ is equivalent to TotP = FP+ and P = PP, and give examples of FP+-functions such that if TotP is closed under composition with them, then it is closed under composition with FP+.

Keywords: computational complexity, counting problems, closure properties, #P

Publication based on the results of: New methods in the study of formal computation models, computer systems and related theoretical computer science problems (2025)

In book

19th Annual Conference, TAMC 2025, Jinan, China, September 19–21, 2025, Proceedings. Theory and Applications of Models of Computation. Lecture Notes in Computer Science (LNCS, volume 16084)

Vol. 16084. , Springer, 2026.