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}_{+}\) .

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Closure Properties and Characterizations of TotP

  • Yaroslav Ivanashev

摘要

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}_{+}\) .