2026/07/31 by Yaroslav Ivanashev
Computer Science · #cs.CC
arxiv created 2026/07/31 · arxiv updated 2026/08/04
The classes MidP, MedP, and \smallMedP contain functions that compute the median solution for certain types of problems. In this paper, for these classes we introduce analogous classes of functions that compute the k-th solution, where k is an order function that depends on the input. We prove that the classes MidP, MedP, and \smallMedP are polynomial-time 1-Turing inter-reducible with the corresponding classes, where the order function is from FP or FP#P. For MedP we also prove that it coincides with the corresponding classes, where the order function is from FP or #P. For several inclusions between function classes we give equivalent inclusions between language classes. In particular, we establish inclusion relations between MaxP and median classes MidP, MedP, and \smallMedP. We also prove that NPSVt ⊆ MaxP ⊆ FPNP and both inclusions are proper if and only if NP ≠ coNP.