Polynomial-time word preprocessing before an oracle query
ProvedAPSCounting893.Main.native_polynomial_oracle_preimageapscounting-hierarchyoracle-machinespolynomial-time
Let be any language of finite binary words and let be computed by a fixed deterministic binary multitape Turing machine in polynomial time. Then
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 .
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 sorrySource
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.