Theorem 3.10 — An oracle separates SSLB from prAM-hardness
OpenAMRangeAvoid.Characterization.Supplement.theorem_3_10complexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1range-avoidance
There exists a binary language oracle such that relativized Structured Set Lower Bound is not hard for relativized promise Arthur–Merlin under deterministic polynomial-time many-one reductions:
Both SSLB circuits, the Arthur–Merlin verifier and the reduction machine may query this same oracle. The assertion rules out hardness even when reductions have oracle access.
Differences from the source:
- encoding: a binary language oracle and relativized polynomial time → a Boolean membership function and finite TM2 programs with an explicit query stack; reason: the same oracle is used for gates, verifiers and reductions, and every non-oracle step is charged
Preamble
import Definitions.Def_AMRangeAvoid_Characterization_Supplement_Oracle import Definitions.Def_AMRangeAvoid_Characterization_SSLB
Formal statement
namespace AMRangeAvoid.Characterization.Supplement theorem theorem_3_10 : ∃ O : Bits → Bool, ¬ IsPrAMHardO O (OracleSSLB O) := by sorry end AMRangeAvoid.Characterization.Supplement
Source
Zeyong Li, STOC 2027 submission #502 (October 2026), Theorem 3.10, printed p.19 (PDF p.21); https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/502.pdf