On the Complexity of Computing Outputs of a Metric Turing Machine

Abstract

The classes MidP, MedP, and $\small{\overline{\text{MedP}}}$ 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 $\small{\overline{\text{MedP}}}$ are polynomial-time 1-Turing inter-reducible with the corresponding classes, where the order function is from FP or FP$^{\text{#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 $\small{\overline{\text{MedP}}}$. We also prove that NPSV$_{\text{t}} \subseteq$ MaxP $\subseteq$ FP$^{\text{NP}}$ and both inclusions are proper if and only if NP $\neq$ coNP.