On closure properties of TotP

Abstract

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 second definition of the class TotP in terms of certificates and verifiers, and present a few natural closure properties of this class. We also prove that the closure of TotP under left composition with the class 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+.

Categories