Uniform bounded threshold search with one oracle
ProvedAPSCounting893.Main.bounded_threshold_search_with_oracleapscomplexity-theoryoracle-machines
Fix an oracle language . There is one total binary-word function computable by a deterministic polynomial-time oracle machine such that the following holds for every word and every integer . If
then
The machine writes its answer to the physical output tape. The same machine handles every input length and threshold. This supplies the bounded search step that converts rank-threshold queries into image dimension in Lemma 6.1.
Preamble
import Definitions.Def_APSCounting893_Main_OracleProofPrimitives set_option autoImplicit false open APSCounting893.Main
Formal statement
theorem APSCounting893.Main.bounded_threshold_search_with_oracle (A : Language) :
∃ f : Word → Word,FunctionInPWithOracle A f ∧
∀ (x : Word) (r : ℕ),r≤x.length →
(∀ j : ℕ,j≤x.length → (A (pairWord x (encodeNat j)) ↔ j≤r)) → f x=encodeNat r := by sorrySource
Bounded search component of Agarwal, Hari, Pandey, Shukla, STOC 2027 submission #893, Lemma 6.1 and proof, p. 23; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/893.pdf