{"id":"e69a2c39-b77f-4ade-9a57-0b36f7c9a844","arxiv_id":"2608.00283","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Kth-output and kth-witness classes are 1-Turing inter-reducible with the median classes and FP^{#P}; the multiplicity-median class MedP equals its kth-output version for every FP or #P order function.","lead":"This paper introduces complexity classes for computing the k-th output or witness of a nondeterministic machine, where the rank k is itself a function of the input. It proves these k-th classes are polynomial-time Turing-equivalent to the median-output classes and to FP^{#P}, and derives conditional collapses involving MaxP, PP, and SPP.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.2's proof is invalid: adding one rejecting path can destroy the strict PP majority when the original margin is 1; the lemma needs a gap-amplification argument.","rationale":"The reader identified Lemma 3.2's normalization as the weakest assumption, and our stress-test confirms that the proof of that lemma is flawed in a way that is directly load-bearing for the main result. Adding one rejecting path to a PP machine does not always preserve strict majority; the boundary case A=R+1 breaks it. This is not a mere technicality: Theorem 3.1 uses the lemma to construct a witness set where every query has the same odd path count, and the median witness is shown to contain correct oracle answers by comparing accepting vs. rejecting path counts. If the path-count normalization cannot be made to preserve the PP majority, the entire binary-search/witness construction fails. However, the lemma is true with a standard gap-amplification argument (e.g., using independent copies to amplify the gap before adding a path), so the flaw is repairable. The other flagged issues — the self-cited [4] for the '#P oracle can compute two #P functions' property and the informal majority-tree argument — are not load-bearing in the same way; the former is a standard fact, and the latter can be justified by equal-depth padding and the uniform path count. Thus the paper's central claim is plausible but requires a corrected Lemma 3.2 proof. The reader's CONDITIONAL verdict is appropriate, and our analysis does not move it.","tokens_in":7873,"tokens_out":27168,"duration_ms":240187,"concrete_test":"Take a PP language L and an NPTM M with A = R+1 accepting/rejecting paths (e.g., a machine with one accepting and zero rejecting paths on a satisfiable instance). Apply the proof of Lemma 3.2: standardize path lengths, then add one rejecting path. Check that the resulting machine has equal accepting/rejecting counts, violating condition 1. Then test the standard repair: take k independent copies of M, accept if all k copies accept, so the gap becomes (A-R)^k; choose k so the gap is at least 2, then add a single rejecting path to make the total odd and length-dependent. Verify that this machine satisfies all three conditions of Lemma 3.2. If the repair works, the central chain survives; if not, Theorems 3.1 and 4.3 collapse.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central chain in Theorem 4.3 and the majority-tree argument in Theorem 5.2 both depend on Lemma 3.2, which asserts that every PP language is witnessed by an NPTM with strictly more accepting than rejecting paths, an odd total path count that depends only on input length, and an FP-computable path count. The proof of Lemma 3.2 as written is incorrect: after standardizing path length, it says 'one rejecting path should be added to make the number of paths odd.' If the original machine has exactly one more accepting than rejecting path (A = R+1), adding one rejecting path makes A' = R' and the strict majority is lost. If the original machine has A = R (a 'don't care' case for PP), adding one accepting path would incorrectly create a majority. Thus the proposed construction does not preserve the language. This is load-bearing because Theorem 3.1's binary-search/witness encoding requires every oracle query to use a machine with a known, odd, length-dependent path count and a strict majority. The lemma itself is true via standard PP gap amplification (e.g., taking k independent copies to make the gap at least 2, then adding one path), but the paper does not provide that argument. The gap is repairable, so this is not a refutation, but the proof as written is insufficient for the main theorem.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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].","tokens_in":8178,"tokens_out":27836,"duration_ms":292250,"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":[{"comment":"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).","section":"§5, Theorem 5.2(3)"},{"comment":"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.","section":"§5, Theorem 5.2(1)"},{"comment":"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.","section":"§4, Lemma 4.1 and §5, MedP=MaxMCP"}],"minor_comments":[{"comment":"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.","section":"§3, Lemma 3.2"},{"comment":"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.","section":"Notation"},{"comment":"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.","section":"§5, Theorem 5.2(1)"},{"comment":"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.","section":"§6, Theorem 6.3"},{"comment":"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.","section":"§6, Proposition 6.4"}],"recommendation":"major_revision","confidential_remarks":"The central chain and Section 6 characterizations are plausible and would be of interest, but the proof of Theorem 5.2 is not at the standard of a journal submission. In particular, the majority-tree argument in Theorem 5.2(3) is incorrect as written, and the multiplicity construction in Theorem 5.2(1) is under-specified. I would ask the author to rewrite Section 5 carefully, either by supplying a complete proof of MedP=MaxMCP and KthOutput_seq(#P)⊆MedP or by citing a published proof. I would also ask that the self-citation [4] be replaced with a self-contained argument for the two-#P-queries-in-one fact."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat'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.\n\nThe 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.\n\nThe 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.\n\nThe 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.\n\nThis 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.","headline":"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.","tokens_in":8670,"tokens_out":9778,"would_cite":true,"duration_ms":91636,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q15","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["metric Turing machine","median computation","k-th output","k-th witness","FP^#P","PP","MaxP","counting complexity"],"falsifier":"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.","tokens_in":7746,"feed_emoji":"🧮","tokens_out":11354,"duration_ms":110572,"temperature":0.7,"pith_summary":"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.","feed_headline":"Computing the k-th answer is equivalent to computing the median","feed_subtitle":"A chain of 1-Turing equivalences collapses FP^#P, median classes, and k-th output classes; for the witness-median class the equality is exac","key_machinery":"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","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Median and k-th outputs are 1-Turing equivalent","One Turing query collapses median and k-th output classes","k-th output equals median up to one query","Median vs k-th: identical complexity under 1-Turing","Computing the k-th answer reduces to median in one call"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Median and k-th outputs are 1-Turing equivalent","One Turing query collapses median and k-th output classes","k-th output equals median up to one query","Median vs k-th: identical complexity under 1-Turing","Computing the k-th answer reduces to median in one call"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00118,"raw_usage":{"total_tokens":4737,"prompt_tokens":796,"completion_tokens":3941,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":540,"completion_tokens_details":{"reasoning_tokens":3861}},"tokens_in":540,"tokens_out":3941,"duration_ms":27215,"temperature":1.0,"reasoning_tokens":3861,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T00:51:38.211671+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}