Proof of Theorem 3.5, p. 9 β if the final states for A β π and A_y are within 1/13, M fails on β_A or on β_{A_y}
ProvedBBBV.RandomOracle.fails_one_of_closeLet be a -query algorithm whose queries are strings of and whose answers are in . Let be an oracle under which has no preimage, let , and let be the oracle with and for . If the final states of with oracle and with oracle satisfy
then does not both decide " has a preimage under " with oracle and decide " has a preimage under " with oracle .
In the paper's words, fails to accept either or on input : the acceptance probabilities differ by at most , while bounded-error decision requires acceptance probability at most under (where ) and at least under (where ).
Formalization Note "Deciding" means bounded error with thresholds and on both sides (Β§2, p. 5). The input is fixed and absorbed into the algorithm's initial state.
import Mathlib import Definitions.Def_BBBV_RandomOracle_QueryModel
namespace BBBV.RandomOracle
theorem fails_one_of_close {n : β} {W : Type} [Fintype W] [DecidableEq W] {T : β}
(M : QueryAlg (Str n) (Str n) W T) (A : Str n β Str n) (hA : NoInverse A) (y : Str n)
(h : βfinal M (fun _ => A) - final M (fun _ => Function.update A y (ones n))β β€ 1 / 13) :
Β¬ (Decides M (fun _ => A) (β x, A x = ones n) β§
Decides M (fun _ => Function.update A y (ones n))
(β x, Function.update A y (ones n) x = ones n)) := by sorry
end BBBV.RandomOracle
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.