3 papers
cs.CC2026
On the Complexity of Computing Outputs of a Metric Turing Machine
Yaroslav Ivanashev
The classes MidP, MedP, and contain functions that compute the median solution for certain types of problems. In this paper, for these classes we i…
cs.CC2025
Low Sets and Closure Properties of Counting Function Classes
Yaroslav Ivanashev
A language L is low for a relativizable complexity class C, if C = C. For the classes #P, GapP, and SpanP the exact low classes of languages are known: Low(#P) = UP $\…
cs.CC2025
Closure Properties and Characterizations of TotP
Yaroslav Ivanashev
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…