Acceptance of a coAM procedure (Definition 7.4)
DefinitionAvoidPlast_Supplement_coAMOnecomplexity-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1range-avoidancespace-bounded-computation
For a coAM procedure with deterministic verifier , iff
Definition code
import Mathlib
import Definitions.Def_AvoidPlast_Accepts
import Definitions.Def_AvoidPlast_Machine
import Definitions.Def_AvoidPlast_prob
namespace AvoidPlast.Supplement
open AvoidPlast
/-- `D(x, y) = 1` for a coAM procedure (Li–Tell, *Trading Time, Space, and Alternations: General Plasticity for Algorithms from Hardness of Range Avoidance*, STOC 2027 submission manuscript (sha256 e1ff3a9e…d6728), Definition 7.4, p.41): over the coins
`ρ ∈ {0,1}^{r_D(n)}`, `Pr_ρ[∃ w ∈ {0,1}^{w_D(n)} : D(x, y, ρ, w) = 0] ≤ 1/3`, where `n = |x|` and
`D(x, y, ρ, w) = 0` means that the deterministic verifier does not accept. -/
def coAMOne (D : Machine 4) (rD wD : ℕ → ℕ) (x y : List Bool) : Prop :=
prob (rD x.length) (fun ρ => ∃ w : List Bool, w.length = wD x.length ∧ ¬ Accepts D ![x, y, ρ, w])
≤ 1 / 3
end AvoidPlast.Supplement
Source
Li–Tell, Trading Time, Space, and Alternations: General Plasticity for Algorithms from Hardness of Range Avoidance, STOC 2027 submission (manuscript sha256 e1ff3a9e…), Definition 7.4, p.41 (PDF p.43)