Closure Properties and Characterizations of TotP
摘要
The class \(\textsf{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 \(\textsf{TotP}\) , analogous to a standard definition of \(\mathsf {\#P}\) . From a new characterization of \(\textsf{TotP}\) it follows that many well known \(\mathsf {\#P}\) problems belong to \(\textsf{TotP}\) , and \(\textsf{TotP}= \mathsf {\#P}\) if and only if \(\textsf{P}= \textsf{NP}\) . We show that \(\textsf{TotP}\) has several closure properties of \(\mathsf {\#P}\) and \(\textsf{GapP}\) , and also properties that are not known to hold for \(\mathsf {\#P}\) and \(\textsf{GapP}\) . We also prove that the closure of \(\textsf{TotP}\) under left composition with \(\textsf{FP}_{+}\) is equivalent to \(\textsf{TotP}= \textsf{FP}_{+}\) and \(\textsf{P}= \textsf{PP}\) , and give examples of \(\textsf{FP}_{+}\) -functions such that if \(\textsf{TotP}\) is closed under composition with them, then it is closed under composition with \(\textsf{FP}_{+}\) .