Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Polynomial-time word preprocessing before an oracle query

Proved
APSCounting893.Main.native_polynomial_oracle_preimage

by Shuze Chen · Nov 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

apscounting-hierarchyoracle-machinespolynomial-time

Let AAA be any language of finite binary words and let fff be computed by a fixed deterministic binary multitape Turing machine in polynomial time. Then

f−1(A)∈PA.f^{-1}(A)\in\mathrm{P}^{A}.f−1(A)∈PA.

The destination is the physical finite oracle-machine model used for the APS counting hierarchy. One fixed machine and one polynomial clock work for every input word, and the oracle receives the actual output word f(x)f(x)f(x).

This interface permits uniform gate-address and coefficient-query computations to be performed before calls to lower-level counting-hierarchy languages. Its hypothesis uses actual native Turing-machine computation and a uniform time bound.

Preamble
import Definitions.Def_APSCounting893_Main_CountingHierarchy
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_PolyTime
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Encodings_List
set_option autoImplicit false
open APSCounting893.Main
Formal statement
theorem APSCounting893.Main.native_polynomial_oracle_preimage
    (f : Word → Word)
    (hf : Turing.MultiTapeTM.ComputableInPolyTime f Turing.MultiTapeTM.encBits Turing.MultiTapeTM.encBits)
    (A : Language) : InOracleP A (fun x => A (f x)) := by sorry
Source
Finite-machine preprocessing interface for the gate-evaluation argument of Andrews, Garg and Schost, Hilbert’s Nullstellensatz is in the Counting Hierarchy, https://arxiv.org/abs/2602.17904, Lemma 6.3, pp. 45–46; used in Agarwal, Hari, Pandey and Shukla, STOC 2027 submission #893, Theorem 6.4, pp. 25–26, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/893.pdf. Native finite-machine semantics: https://github.com/cslib-community/complexitylib/blob/0ebd4671c2e7278a91f5671c11109bb254ae413c/Complexity/Computability/Machines/Turing/MultiTape/PolyTime.lean.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me