The paper gives exact characterizations of low languages and low functions for the counting classes TotP, #P, GapP, and SpanP, and links their closure under composition to collapses such as PP=UP and PP=NP.
In: Annual Confer- ence on Theory and Applications of Models of Computation
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
fields
cs.CC 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Low Sets and Closure Properties of Counting Function Classes
The paper gives exact characterizations of low languages and low functions for the counting classes TotP, #P, GapP, and SpanP, and links their closure under composition to collapses such as PP=UP and PP=NP.