On the Complexity of Computing Outputs of a Metric Turing Machine

Yaroslav Ivanashev

REVIEW 3 major objections 5 minor 14 references

On the Complexity of Computing Outputs of a Metric Turing Machine

T0 review · 3 major / 5 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that computing the k-th output or witness of a nondeterministic machine is polynomial-time 1-Turing equivalent to computing its median output.

desk verdict A believable extension of the median-class story to k-th output/witness functions; the main result is likely correct, but the write-up needs a fix in Lemma 3.2 and more detail in Theorem 5.2. read the letter →

arxiv 2608.00283 v1 pith:VXFNAWR2 submitted 2026-07-31 cs.CC

Yaroslav Ivanashev This is my paper · ORCID

classification cs.CC MSC 68Q1568Q17

keywords metricTuringmachinemediancomputationk-thoutputwitnessFP^#PPPMaxPcountingcomplexity

topics P versus NP

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper introduces classes of functions that return the k-th output or witness of a nondeterministic polynomial-time machine, where k is itself an input-dependent order function. It proves that these k-th output classes are exactly as hard as the median-output classes—the set-median class MidP, the multiplicity-median class MedP, and the witness-median class MedP—each computable with a single oracle call to the other. The central theorem is a chain of equalities showing that FP^#P and all these function classes lie in the same 1-Turing degree. For the witness-median class, the paper proves an even stronger coincidence: it equals the class of functions that compute the k-th output in a sorted multiset, for any k computable in FP or #P. This matters because it unifies optimization and counting: locating a specified ordered output is no harder than locating the middle one.

What carries the argument

The central mechanism is a normal-form lemma giving every PP language a witness machine with an odd number of paths that depends only on the input length and is computable in polynomial time. This guarantees that when oracle answers and witness paths are encoded as fixed-length strings, every partial prefix extends to the same number of complete witnesses. Consequently, the lexicographically middle witness must decode the correct oracle answers step by step, which turns a single median query into a binary search that can extract the k-th witness or output for any order function from FP or FP^#P. The same uniform-extension property underlies the MaxMCP characterization used to prove the exact

What would settle it

Construct a language L in PP and a machine witnessing the majority for which no polynomial-time padding can make the total path count odd, length-only, and majority-preserving; equivalently, run the construction of Theorem 3.1 on a concrete PP instance and check whether the median witness always decodes the correct oracle answers—if flipping one oracle answer changes the median, the uniform-extension property fails and the chain would be false.

Watch

Extended reading notes

Core claim

The central discovery is that the function classes defined by median outputs and by k-th outputs (or witnesses) coincide up to a single adaptive oracle query: FP^#P equals FP^C[1] for every C among the multiplicity median class MedP, the set median class MidP, the witness median class MedP, and the corresponding k-th output classes KthWitness(FP), KthWitness(FP^#P), KthOutput(FP), KthOutput(FP^#P), KthOutput_seq(FP), and KthOutput_seq(FP^#P). For the witness-median class MedP, it proves the outright equality MedP = MaxMCP = KthOutput_seq(FP) = KthOutput_seq(#P), not just Turing equivalence. It also gives language-class characterizations: NPSV_t ⊆ MaxP ⊆ FP^NP with properness iff NP ≠ coNP, a

Load-bearing premise

The reductions hinge on Lemma 3.2, which claims that every PP language can be witnessed by a machine whose total number of paths is odd, depends only on the input length, and is computable in polynomial time; if this normalization cannot be achieved while preserving the PP majority, the middle-witness constructions collapse.

Editorial extensions

If this is right

FP^#P can be computed with a single query to any of the k-th output or k-th witness classes, and every such class can be computed with a single query to FP^#P, so they all share one 1-Turing degree.
For the witness-median class, the k-th-output-in-a-sequence classes with order functions from FP or #P are equal to it exactly, not merely reducible to it.
The placement NPSV_t ⊆ MaxP ⊆ FP^NP becomes a sharp characterization: the inclusions are proper unless NP = coNP, linking the complexity of optimization functions directly to the NP versus coNP question.
MaxP is contained in both median classes MidP and MedP, and collapses such as MedP = MaxP are equivalent to PP = NP, giving new equivalent forms of known open problems.
Inclusions between function classes are shown to be equivalent to inclusions between language classes, e.g., SpanP ⊆ MedP iff NP ⊆ SPP, so progress on either side transfers to the other.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same uniform-extension technique likely extends to any polynomial-time computable quantile (e.g., the 30th percentile), not just the median, yielding the same 1-Turing collapse; the paper does not explore this.
Because the proofs relativize, any separation between two classes in the chain would require a non-relativizing argument, suggesting the collapse is robust while also explaining why lower-bound proofs are hard.
The exact equality MedP = KthOutput_seq(#P) suggests that closure properties of MedP could be studied through k-th output queries, possibly yielding new closure results for counting classes.
The characterization of MaxP in terms of NP versus coNP indicates that the difficulty of maximization over NP computations is essentially the difficulty of complementing NP languages, which may be a useful lens for optimizing other function classes.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Read the arXiv paper 2608.00283. My take: the central theorems are believable and new — the k-th output/witness classes are a natural extension of the median classes, and the equality MedP = KthOutput_seq(FP) = KthOutput_seq(#P) is a clean characterization. The chain in Theorem 4.3 also ties everything to FP^#P. If the proofs check out, this is a useful addition for anyone working on counting classes.

What's actually new: the class definitions and the equality claims. The proofs are mostly adaptations of known binary-search and padding tricks, which is fine; the field runs on those.

The main issue is the proof of Lemma 3.2. The author says to standardize path length, then add one rejecting path to make the total odd. That works only if the path count is even (so the majority margin is at least 2). If the machine has zero nondeterministic steps, you get a single accepting path and a single rejecting path after the addition — a tie. This isn't a fatal flaw: add a dummy nondeterministic branch at the start to double the paths, then add one rejecting path. That fixes it. But the lemma is load-bearing for Theorems 3.1 and 5.2, so the write-up needs the fix.

The other soft spot is the majority-tree argument in Theorem 5.2, step 3. It's compressed into a few sentences. I think it's probably right, but a referee will want more detail. Also, Lemma 4.1 invokes the author's own [4] for a #P closure property; that's okay if the source is accessible, but citing a more standard reference or including the proof would be better. And the notation for MedP vs the witness-median class is easy to mix up; in the version I read the overline didn't render at all, which is worth fixing.

The reader's stress-test concern about Lemma 3.2 is valid in that edge case, but the lemma is true and easily repaired. I don't see a load-bearing flaw anywhere else. The citation pattern is standard; self-citation is used as a tool, not to preempt conclusions.

This paper deserves peer review. Send it to a referee who knows the counting-class literature. After a revision that fixes Lemma 3.2 and expands Theorem 5.2, it should be acceptable.

Referee Report

3 major / 5 minor

Summary. The paper introduces order-function analogues of the median classes MidP, MedP, and \overline{MedP}, called KthOutput(C), KthOutput_seq(C), and KthWitness(C) for order functions from FP, FP^#P, or #P. Its main claims are: (i) Theorem 4.3, a polynomial-time 1-Turing equivalence chain FP^#P = FP^{MedP}[1] = FP^{KthWitness(FP)}[1] = ... = FP^{KthOutput_seq(FP^#P)}[1]; (ii) Theorem 5.2, an equality MedP = MaxMCP = KthOutput_seq(FP) = KthOutput_seq(#P); and (iii) Section 6, several equivalence statements between inclusions of function classes and inclusions of language classes, e.g., MaxP is properly between NPSV_t and FP^NP iff NP ≠ coNP. The paper also offers a simplified proof of the known equality FP^#P = FP^{MedP}[1].

Significance. If correct, the results give a clean and useful picture: for 1-Turing reductions, median oracles are interchangeable with k-th-output/witness oracles for MidP, MedP, and \overline{MedP} over FP and FP^#P order functions, and for MedP the k-th-output class coincides with MedP itself. The Section 6 inclusion characterizations (e.g., MedP=MaxP iff NP=PP, SpanP⊆\overline{MedP} iff NP⊆SPP) are attractive and would be a solid contribution to the complexity theory literature. The paper is clearly organized and the central chain is the right way to frame these results. However, several load-bearing proof steps in Section 5 are not sufficiently justified as written, and at least one key lemma in Section 4 depends on an unpublished self-citation. These issues should be fixed before the paper can be accepted.

major comments (3)

[§5, Theorem 5.2(3)] The proof of MaxMCP⊆MedP asserts that because at every simulation of N more than half of N's paths make the correct decision, 'the path with the middle output has correct decisions'. This is not valid. If each simulation has only a small majority, say A=R+1 paths, then after d binary-search levels the fraction of M-paths following the all-correct sequence is (A/(A+R))^d, which can be much smaller than 1/2 for polynomial d. The global lower median therefore need not lie on the all-correct path; a majority at each node does not imply a majority at the root in a tree. The proof needs either an amplified gap (a PP machine whose accepting probability is overwhelmingly close to 1) or a different counting argument. The same flaw propagates to item (4), MaxMCP⊆KthOutput_seq(FP).
[§5, Theorem 5.2(1)] In the inclusion KthOutput_seq(#P)⊆MedP, the construction adds 'k smaller numbers' and '2g(x) copies' of a large value to the output sequence. This is not realized by an NPTM in the stated multiplicities. A #P machine for g has, in general, t(x) total paths with only g(x) accepting paths; the t(x)-g(x) rejecting paths must accept and output something in a metric machine, adding unwanted elements to the output sequence. The proof does not specify where these extra outputs go or why they do not shift the median. For arbitrary #P functions one cannot assume a machine with exactly g(x) or 2g(x) total paths. This is a central step in one of the paper's main equalities and needs a detailed construction or a citation to a published proof.
[§4, Lemma 4.1 and §5, MedP=MaxMCP] Lemma 4.1(1) relies on the author's own paper [4] for the nontrivial fact that 'one #P oracle can be used to compute two #P functions'. Since [4] is not included in the manuscript and appears to be a self-citation, this closure property is load-bearing and unverifiable from the text. Likewise, the equality MedP=MaxMCP is cited to an unpublished manuscript [14, Lemma 4.10], while the proof in Theorem 5.2 is a sketch. These dependencies should be made removable by providing full proofs or by citing publicly accessible published work.

minor comments (5)

[§3, Lemma 3.2] The stress-test concern about Lemma 3.2 does not actually land, but the proof should say explicitly why adding one rejecting path is safe. After path-length standardization the machine has exactly 2^m paths, so A+R is even and A−R is even; hence A>R implies A−R≥2, and adding one rejecting path preserves A'>R'. Adding this one sentence would make the argument rigorous and remove any appearance of a margin-1 gap.
[Notation] The overline in \overline{MedP} is missing in several displays and in the abstract (the class is repeatedly printed as 'MedP'). This makes the text hard to parse in places and should be fixed globally.
[§5, Theorem 5.2(1)] The phrase 'k smaller numbers' is informal: k is the number of paths of the metric machine M, which depends on x and can be exponential in |x|. The construction should state explicitly how the metric NPTM for the MedP function generates exactly k additional paths without disturbing the required multiplicities.
[§6, Theorem 6.3] The proofs of the right-to-left implications are very terse and rely on several inclusions from [13] (e.g., GapP⊆\overline{MedP}, #P^NP−FP⊆MidP) without restating them. This is acceptable if the cited results are standard, but the paper would benefit from stating the exact inclusions used and where each direction of the equivalences is proved.
[§6, Proposition 6.4] In the proof, the equality FP^PP = MaxP under the assumption NP=PP is used implicitly. Since the proposition is one of the paper's new contributions, this equality should be derived explicitly from Proposition 6.4 and the hypothesis.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the main equivalence chain rests on independent prior reductions; the sole self-citation is a minor non-load-bearing technical oracle fact.

full rationale

The central chain in Theorem 4.3 and the equality in Theorem 5.2 are derived from independent prior characterizations by Toda and by Vollmer-Wagner (FP^#P = FP^{MidP}[1] = FP^{MedP}[1] = FP^{overline{MedP}}[1]), together with new binary-search and path-extension constructions. The new KthOutput and KthWitness inclusions are proven by explicit reductions: for example, to put the g(x)-th output at the median, the paper extends the output sequence with k small values and 2g(x) copies of a large value. This is a construction, not a definition of the conclusion into the premise. The only self-citation is reference [4], used in Lemma 4.1 to justify that one #P oracle can encode two #P functions. That fact is a standard, externally checkable closure property and is not the source of the main equivalences, so it does not make the derivation circular. The proof gap in Lemma 3.2 (adding one rejecting path can destroy a one-vote PP majority) is a correctness concern about the proof as written, not a circularity: it does not show that any theorem assumes its own conclusion. Overall, no load-bearing step reduces by construction to its own inputs.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The paper has no fitted parameters and introduces no physical or mathematical entities beyond new function-class definitions. Its central claims rest on standard counting-complexity theorems and one self-cited closure property [4]; no ad-hoc axioms are introduced.

assumptions (7)

standard math FP^{#P} = FP^{PP}
Used in Theorem 3.1 to reduce FP^{#P} to a PP oracle.
standard math SpanP ⊆ FP^{#P}
Used in Lemma 4.2 for binary search over distinct outputs, citing Toda-Watanabe [10].
standard math One #P oracle query can compute two #P functions
Used in Lemma 4.1 to compute g(x) and witness counts together; cited to the author's own [4].
standard math GapP^{SPP} = GapP and the relativized version GapP^{SPP^{NP}} = GapP^{NP}
Used in Theorem 6.3 and Proposition 6.7 to collapse oracle hierarchies, citing Fenner-Fortnow-Kurtz [3] and Mahajan et al. [7].
standard math NPSV_t = FP^{NP ∩ coNP}
Used in Proposition 6.4 to relate MaxP to FP^{NP}, citing Selman [8] and Book-Long-Selman [1,2].
standard math U/S operator characterizations: U·MedP=SPP, S·MedP=PP, U·MedP=PP, S·MedP=PP, U·MidP=SPP^{NP}, S·MidP=PP^{NP}
Used throughout Section 6 to convert function-class inclusions into language-class inclusions, citing Vollmer-Wagner [13].
standard math GapP ⊆ MedP and #P^{NP} − FP ⊆ MidP
Used in Theorem 6.3 and Proposition 6.7 to derive containments of counting classes, citing Vollmer-Wagner [13].

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the Complexity of Computing Outputs of a Metric Turing Machine." pith.science (2026). https://pith.science/paper/VXFNAWR2

@misc{pith2026260800283,
  author       = {Pith},
  title        = {Pith review of: On the Complexity of Computing Outputs of a Metric Turing Machine},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VXFNAWR2}},
  note         = {Machine review of arXiv:2608.00283}
}

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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references

[4]

Dok- lady Rossiiskoi akademii nauk

Ivanashev, Y.: Low sets and closure properties of counting function classes. Dok- lady Rossiiskoi akademii nauk. Matematika, informatika, protsessy upravleniya / Doklady Mathematics529, 93–101 (2026)

2026
[1]

SIAM Journal on Computing13(3), 461–487 (1984)

Book, R.V., Long, T.J., Selman, A.L.: Quantitative relativizations of complexity classes. SIAM Journal on Computing13(3), 461–487 (1984)

1984
[2]

Journal of Computer and System Sciences30(3), 395–413 (1985)

Book, R.V., Long, T.J., Selman, A.L.: Qualitative relativizations of complexity classes. Journal of Computer and System Sciences30(3), 395–413 (1985)

1985
[3]

Journal of Computer and System Sciences48(1), 116–148 (1994)

Fenner, S.A., Fortnow, L.J., Kurtz, S.A.: Gap-definable counting classes. Journal of Computer and System Sciences48(1), 116–148 (1994)

1994
[5]

Acta Infor- matica26(4), 363–379 (1989)

Köbler, J., Schöning, U., Torán, J.: On counting and approximation. Acta Infor- matica26(4), 363–379 (1989)

1989
[6]

Journal of Computer and System Sciences36(3), 490–509 (1988)

Krentel, M.W.: The complexity of optimization problems. Journal of Computer and System Sciences36(3), 490–509 (1988)

1988
[7]

Mahajan, M., Thierauf, T., Vinodchandran, N.: A note on SpanP functions. Inf. Process. Lett.51(1), 7–10 (1994) 10 Y. Ivanashev

1994
[8]

Journal of Computer and System Sciences48(2), 357–381 (1994)

Selman, A.L.: A taxonomy of complexity classes of functions. Journal of Computer and System Sciences48(2), 357–381 (1994)

1994

Show all 14 references

[9]

Journal of Computer and System Sciences49(1), 1–17 (1994)

Toda, S.: Simple characterizations of P(#P) and complete problems. Journal of Computer and System Sciences49(1), 1–17 (1994)

1994
[10]

Theoretical Computer Science100(1), 205–221 (1992)

Toda, S., Watanabe, O.: Polynomial-time 1-Turing reductions from #PH to #P. Theoretical Computer Science100(1), 205–221 (1992)

1992
[11]

Theoretical computer science8(2), 189–201 (1979)

Valiant, L.G.: The complexity of computing the permanent. Theoretical computer science8(2), 189–201 (1979)

1979
[12]

In: Annual Sym- posium on Theoretical Aspects of Computer Science

Vollmer, H.: On different reducibility notions for function classes. In: Annual Sym- posium on Theoretical Aspects of Computer Science. pp. 449–460. Springer (1994)

1994
[13]

Interna- tional Journal of Foundations of Computer Science4(04), 293–307 (1993)

Vollmer, H., Wagner, K.W.: The complexity of finding middle elements. Interna- tional Journal of Foundations of Computer Science4(04), 293–307 (1993)

1993
[14]

Univ., Inst

Vollmer, H., Wagner, K.W.: Classes of counting functions and complexity theoretic operators. Univ., Inst. für Informatik (1996)

1996

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.

[1] [4]

Dok- lady Rossiiskoi akademii nauk

Ivanashev, Y.: Low sets and closure properties of counting function classes. Dok- lady Rossiiskoi akademii nauk. Matematika, informatika, protsessy upravleniya / Doklady Mathematics529, 93–101 (2026)

2026

[2] [1]

SIAM Journal on Computing13(3), 461–487 (1984)

Book, R.V., Long, T.J., Selman, A.L.: Quantitative relativizations of complexity classes. SIAM Journal on Computing13(3), 461–487 (1984)

1984

[3] [2]

Journal of Computer and System Sciences30(3), 395–413 (1985)

Book, R.V., Long, T.J., Selman, A.L.: Qualitative relativizations of complexity classes. Journal of Computer and System Sciences30(3), 395–413 (1985)

1985

[4] [3]

Journal of Computer and System Sciences48(1), 116–148 (1994)

Fenner, S.A., Fortnow, L.J., Kurtz, S.A.: Gap-definable counting classes. Journal of Computer and System Sciences48(1), 116–148 (1994)

1994

[5] [5]

Acta Infor- matica26(4), 363–379 (1989)

Köbler, J., Schöning, U., Torán, J.: On counting and approximation. Acta Infor- matica26(4), 363–379 (1989)

1989

[6] [6]

Journal of Computer and System Sciences36(3), 490–509 (1988)

Krentel, M.W.: The complexity of optimization problems. Journal of Computer and System Sciences36(3), 490–509 (1988)

1988

[7] [7]

Mahajan, M., Thierauf, T., Vinodchandran, N.: A note on SpanP functions. Inf. Process. Lett.51(1), 7–10 (1994) 10 Y. Ivanashev

1994

[8] [8]

Journal of Computer and System Sciences48(2), 357–381 (1994)

Selman, A.L.: A taxonomy of complexity classes of functions. Journal of Computer and System Sciences48(2), 357–381 (1994)

1994