On the Complexity of Computing Outputs of a Metric Turing Machine

Yaroslav Ivanashev · 2026

Read On the Complexity of Computing Outputs of a Metric Turing Machine by Yaroslav Ivanashev (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2608-00283.txt.

Introduction

Ivanashev studies the complexity of computing outputs of a metric Turing machine. The classes MidP, MedP, and its complement form contain median-computing functions. Those functions return the median solution for set problem types. He adds analogous classes that compute the k-th solution instead. Here k is an order function that depends on the input.

He proves the median classes are polynomial-time inter-reducible with the new ones. That holds when the order function lies in FP or its counting extension. For MedP, the classes coincide outright under those order functions. Several inclusions between function classes get language-class equivalents. Relations between MaxP and the median classes are established. Two inclusions are proper exactly when NP differs from coNP, he shows.

Catalog record

CREATORYaroslav Ivanashev
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE28 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2608.00283

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the Complexity of Computing Outputs of a Metric Turing Machine Yaroslav Ivanashev Abstract The classes 𝖬𝗂𝖽𝖯 \mathsf{MidP} , 𝖬𝖾𝖽𝖯 \mathsf{MedP} , and 𝖬𝖾𝖽𝖯 ¯ \mathsf{\overline{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 k -th solution, where k k is an order function that depends on the input. We prove that the classes 𝖬𝗂𝖽𝖯 \mathsf{MidP} , 𝖬𝖾𝖽𝖯 \mathsf{MedP} , and 𝖬𝖾𝖽𝖯 ¯ \mathsf{\overline{MedP}} are polynomial-time 1-Turing inter-reducible with the corresponding classes, where the order function is from 𝖥𝖯 \mathsf{FP} or 𝖥𝖯 # ​ 𝖯 \mathsf{FP}^{\mathsf{\#P}} . For 𝖬𝖾𝖽𝖯 \mathsf{MedP} we also prove that it coincides with the corresponding classes, where the order function is from 𝖥𝖯 \mathsf{FP} or # ​ 𝖯 \mathsf{\#P} . For several inclusions between function classes we give equivalent inclusions between language classes. In particular, we establish inclusion relations between 𝖬𝖺𝗑𝖯 \mathsf{MaxP} and median classes 𝖬𝗂𝖽𝖯 \mathsf{MidP} , 𝖬𝖾𝖽𝖯 \mathsf{MedP} , and 𝖬𝖾𝖽𝖯 ¯ \mathsf{\overline{MedP}} . We also prove that 𝖭𝖯𝖲𝖵 𝗍 ⊆ 𝖬𝖺𝗑𝖯 ⊆ 𝖥𝖯 𝖭𝖯 \mathsf{NPSV_{t}}\subseteq\mathsf{MaxP}\subseteq\mathsf{FP}^{\mathsf{NP}} and both inclusions are proper if and only if 𝖭𝖯 ≠ 𝖼𝗈𝖭𝖯 \mathsf{NP}\neq\mathsf{coNP} . 1 Introduction Krentel introduced the class \mathsf{OptP} [ 6 ] that consists of functions that are equal to the maximum or minimum output of a nondeterministic polynomial-time bounded Turing Machine (NPTM) that outputs an integer on every computation path (a NPTM with this property is called metric). He also proved that \mathsf{FP}^{\mathsf{OptP}[1]}=\mathsf{FP}^{\mathsf{NP}} and studied complete problems for \mathsf{FP}^{\mathsf{NP}} under polynomial-time 1-Turing reductions. Toda defined a class \mathsf{MidP} that consists of functions that are equal to the median output of a metric NPTM [ 9 ] , proved that \mathsf{FP}^{\mathsf{MidP}[1]}=\mathsf{FP}^{\mathsf{\#P}} , and studied complete problems for \mathsf{FP}^{\mathsf{\#P}} under polynomial-time 1-Turing reductions. Vollmer and Wagner defined two related median classes: \mathsf{MedP} is defined as \mathsf{MidP} except that the multiplicities of outputs are taken into account, and \mathsf{\overline{MedP}} consists of functions that are equal to the median witness of an NP problem [ 13 ] . They also showed that these classes are polynomial-time 1-Turing inter-reducible: \mathsf{FP}^{\mathsf{MidP}[1]}=\mathsf{FP}^{\mathsf{MedP}[1]}=\mathsf{FP}^{\mathsf{\overline{MedP}}[1]}=\mathsf{FP}^{\mathsf{\#P}} . In Section 3 , we give a simplified proof of this result. Vollmer in [ 12 ] studied complete problems under parsimonious reductions for the classes \mathsf{MidP} , \mathsf{MedP} , and \mathsf{\overline{MedP}} . In this paper, for the median classes \mathsf{MidP} , \mathsf{MedP} , and \mathsf{\overline{MedP}} we define their analogs \mathsf{KthOutput}(C) , \mathsf{KthOutput_{seq}}(C) , and \mathsf{KthWitness}(C) , which consist of functions that are equal to the k -th output or witness (instead of median output or witness) for a function k\in C . Toda used a class \mathsf{KthP} [ 9 ] , which is similar to \mathsf{KthOutput}(\mathsf{FP}) but contains partial functions that take two arguments. We use classes of total functions of one argument in order to compare them with \mathsf{MidP} , \mathsf{MedP} , and \mathsf{\overline{MedP}} . In fact, \mathsf{KthP} would be a subset of \mathsf{KthOutput}(\mathsf{FP}) if it contained only total functions, so \mathsf{KthOutput}(\mathsf{FP}) can be considered as a generalization of \mathsf{KthP} that admits different order functions k\in\mathsf{FP} . For example, the problem KthSAT from [ 9 ] belongs to the classes \mathsf{KthOutput}(\mathsf{FP}) and \mathsf{KthWitness}(\mathsf{FP}) (the assignments of formulas should be encoded as integers). In Section 4 , for the classes \mathsf{\overline{MedP}} , \mathsf{MidP} , and \mathsf{MedP} we show that they are polynomial-time 1-Turing inter-reducible with their corresponding classes, where the function k is either in \mathsf{FP} or \mathsf{FP}^{\mathsf{\#P}} : \mathsf{FP}^{\mathsf{\#P}}=\mathsf{FP}^{\mathsf{\overline{MedP}}[1]}=\mathsf{FP}^{\mathsf{KthWitness}(\mathsf{FP})[1]}=\mathsf{FP}^{\mathsf{KthWitness}(\mathsf{FP}^{\mathsf{\#P}})[1]}=\mathsf{FP}^{\mathsf{MidP}[1]}=\mathsf{FP}^{\mathsf{KthOutput}(\mathsf{FP})[1]}=\mathsf{FP}^{\mathsf{KthOutput}(\mathsf{FP}^{\mathsf{\#P}})[1]}=\mathsf{FP}^{\mathsf{MedP}[1]}=\mathsf{FP}^{\mathsf{KthOutput_{seq}}(\mathsf{FP})[1]}\\ =\mathsf{FP}^{\mathsf{KthOutput_{seq}}(\mathsf{FP}^{\mathsf{\#P}})[1]} . In Section 5 , for the class \mathsf{MedP} we prove that it coincides with the corresponding classes \mathsf{KthOutput_{seq}}(\mathsf{FP}) and \mathsf{KthOutput_{seq}}(\mathsf{\#P}) . In Section 6 , for several inclusions between function classes we give equivalent inclusion between language classes. In [ 13 ] , Vollmer and Wagner proved that \mathsf{\overline{MedP}}\subseteq\mathsf{MidP}\cap\mathsf{MedP} and the other inclusions between these classes have implausible implications. For some of these implications we show that they hold in the opposite direction. We prove that \mathsf{FP}^{\mathsf{NP}\cap\mathsf{coNP}}\subseteq\mathsf{MaxP}\subseteq\mathsf{FP}^{\mathsf{NP}} and both inclusions are proper if and only if \mathsf{NP}\neq\mathsf{coNP} . We also prove that \mathsf{MaxP} contains the classes \mathsf{MidP} , \mathsf{MedP} , and \mathsf{\overline{MedP}} if and only if \mathsf{PP}=\mathsf{NP} , and \mathsf{\overline{MedP}} contains the classes \mathsf{SpanP} and \mathsf{MaxP} if and only if \mathsf{NP}\subseteq\mathsf{SPP} . 2 Preliminaries In this paper, we use a standard definition of a nondeterministic polynomial-time bounded Turing machine (NPTM) and binary alphabet \Sigma=\{0,1\} . We assume that the reader is familiar with basic complexity theory notions and classes \mathsf{NP} , \mathsf{PP} , \mathsf{SPP} [ 3 ] , \mathsf{\#P} [ 11 ] , \mathsf{GapP} [ 3 ] , \mathsf{SpanP} [ 5 ] . Definition 2.1 ( [ 6 ] ) A NPTM is called metric if on every branch it outputs a binary number from \mathbb{Z} and accepts. In the definition above, the outputs of a NPTM can be negative numbers (in some reasonable encoding). Krentel defined the class \mathsf{OptP} [ 6 ] as a union of the classes \mathsf{MinP} and \mathsf{MaxP} that we define below. Definition 2.2 [ 6 ] \mathsf{MaxP}=\{max_{M}\ |\ M is a metric NPTM \} , where max_{M}(x) is the maximum value in a set of all outputs of M on input x\in\Sigma^{*} . More precisely, if \{w_{1},\dots,w_{k}\} is the set of all outputs of M on input x and if w_{1}<\ldots<w_{k} , then max_{M}(x)=w_{k} . The class \mathsf{MinP} is defined analogously. In this paper, we will use only the class \mathsf{MaxP} . All results that we prove for this class also hold for the class \mathsf{MinP} . Below we give definitions of median classes that we will consider in this paper. Definition 2.3 1. [ 9 ] \mathsf{MidP}=\{mid_{M}\ |\ M is a metric NPTM \} , where mid_{M}(x) is the median value in a set of all outputs of M on input x\in\Sigma^{*} . More precisely, if \{w_{1},\dots,w_{k}\} is the set of all outputs of M on input x and if w_{1}<\ldots<w_{k} , then mid_{M}(x)=w_{\lfloor(k+1)/2\rfloor} . 2. [ 13 ] \mathsf{MedP}=\{med_{M}\ |\ M is a metric NPTM \} , where med_{M}(x) is the median value in a sequence of all outputs of M on input x\in\Sigma^{*} . More precisely, if w_{1}\leqslant\ldots\leqslant w_{k} is the sequence of all outputs (with multiplicities) of M on input x , then med_{M}(x)=w_{\lfloor(k+1)/2\rfloor} . 3. [ 13 ] The class \mathsf{\overline{MedP}} consists of all functions f for which there exist a language A\in\mathsf{P} and functions l,r\in\mathsf{FP} ( \Sigma^{*}\rightarrow\mathbb{Z} ) such that for every x\in\Sigma^{*} : \displaystyle f(x)=\begin{cases}y_{\lfloor(k+1)/2\rfloor},&\text{if the set $W$ is not empty,}\\ l(x)-1,&\text{$otherwise$,}\end{cases} where W=\{y\in\mathbb{Z}\ |\ l(x)\leqslant y\leqslant r(x)\wedge(x,y)\in A\}=\{y_{1},\dots,y_{k}\} and y_{1}<\ldots<y_{k} . In [ 13 ] , Vollmer and Wagner proved that \mathsf{\overline{MedP}} is a subset of \mathsf{MidP} and \mathsf{MedP} . Theorem 6.3 shows that the other inclusions between these classes are not likely to hold. Proposition 2.4 ( [ 13 ] ) \mathsf{\overline{MedP}}\subseteq\mathsf{MidP}\cap\mathsf{MedP} . For the median classes above we define their analogs, where the functions compute outputs or witnesses of some specific order. Definition 2.5 Let C be a class of functions \Sigma^{*}\rightarrow\mathbb{N} . 1. The class \mathsf{KthOutput}(C) consists of all functions f for which there exist a metric NPTM M and a function g\in C such that for every x\in\Sigma^{*} : \displaystyle f(x)=\begin{cases}w_{g(x)},&\text{if $M$ has at least $g(x)$ outputs on input $x$,}\\ 2^{p(|x|)},&\text{$otherwise$,}\end{cases} where \{w_{1},\dots,w_{k}\} is the set of all outputs

Read the complete text