Theorem 3.9 — SSLB is in promise symmetric polynomial time
OpenAMRangeAvoid.Characterization.Supplement.theorem_3_9complexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1range-avoidance
Structured Set Lower Bound admits one deterministic polynomial-time symmetric predicate and one fixed polynomial witness bound. Every YES input has a first witness forcing acceptance against all second witnesses; every NO input has a second witness forcing rejection against all first witnesses:
This is unconditional membership. No single-valued Avoid solver, oracle separation or additional algorithm is assumed. The promise problem is the published SSLB definition.
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_3_9 : InPromiseS2P SSLB := by sorry end AMRangeAvoid.Characterization.Supplement
Source
Zeyong Li, STOC 2027 submission #502 (October 2026), Theorem 3.9, printed p.18 (PDF p.20); https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/502.pdf