Compilation of polynomial-time batch oracle reductions
ProvedCountOrderings.NFree.batch_oracle_polytimecounting-complexitylinear-extensions
A preprocessing transducer, a packed-query generating transducer, and a transducer on the packed preprocessed input and oracle replies implement a polynomial-time Turing reduction on the published oracle-machine model, provided the packed replies have length polynomial in the preprocessed input length. The query generation is independent of the replies.
Preamble
import Definitions.Def_CountOrderings_NFree_OracleReduction import Definitions.Def_ExactAmpDich_Complexity
Formal statement
namespace CountOrderings.NFree
theorem batch_oracle_polytime
(prepare finish oracle : List Bool → List Bool)
(queries : List Bool → List (List Bool))
(hPrepare : CookLevin.IsPolyTimeComputable prepare)
(hQueries : CookLevin.IsPolyTimeComputable (fun x => packWords (queries x)))
(hFinish : CookLevin.IsPolyTimeComputable finish)
(hAnswers : ∃ c d : ℕ, ∀ x,
(packWords ((queries x).map oracle)).length ≤ CookLevin.polyBound c d x.length) :
ExactAmpDich.TuringReducesTo
(fun x => finish (packWords (prepare x :: (queries (prepare x)).map oracle))) oracle := by sorry
end CountOrderings.NFreeSource
Arenas, Schild and Subercaseaux, Hardness of Counting Orderings: Taking Gadget Amplification to the Limit, STOC 2027 submission #1207, https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/1207.pdf, Appendix A.12, pp. 37–38 (PDF pp. 38–39), proof of Theorem 6.3. This isolates the nonadaptive oracle computation in the reduction, on the published Cook–Levin model.