Theorem 4.2 — Every promise-MA problem reduces to SSLB
OpenAMRangeAvoid.Characterization.Supplement.theorem_4_2complexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1range-avoidance
Let be any promise problem in Merlin–Arthur with perfect completeness and soundness at most . Merlin chooses the witness before Arthur's random string. Then
The conclusion supplies a single total deterministic polynomial-time transducer preserving both promised sides. It applies to promise problems, without assuming a PRG or a solver for range avoidance.
Differences from the source: none.
Preamble
import Definitions.Def_AMRangeAvoid_Characterization_Supplement_Complexity import Definitions.Def_AMRangeAvoid_Characterization_SSLB
Formal statement
namespace AMRangeAvoid.Characterization.Supplement
theorem theorem_4_2 (A : PromiseProblem) (hA : InPrMA A) :
PromiseReduces A SSLB := by sorry
end AMRangeAvoid.Characterization.Supplement
Source
Zeyong Li, STOC 2027 submission #502 (October 2026), Theorem 4.2, printed p.19 (PDF p.21); https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/502.pdf