Theorem 4.4 — Graph Non-Isomorphism reduces to SSLB
OpenAMRangeAvoid.Characterization.Supplement.theorem_4_4complexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1range-avoidance
For pairs of finite simple undirected graphs on a common labeled vertex set, there is a deterministic polynomial-time many-one reduction
A nonisomorphic graph pair maps to a YES instance of SSLB; an isomorphic pair maps to a NO instance with both the size and covering promises. The input does not include automorphism generators. All graph sizes, including zero and one, are retained.
Differences from the source:
- encoding: graph pairs on the common set [n] → binary adjacency matrices on Fin n, with invalid codes assigned to the isomorphism side; reason: relabeling is bijective, and the decidable extension specifies only strings that are not source instances
Preamble
import Definitions.Def_AMRangeAvoid_Characterization_Supplement_Graphs import Definitions.Def_AMRangeAvoid_Characterization_SSLB
Formal statement
namespace AMRangeAvoid.Characterization.Supplement theorem theorem_4_4 : PromiseReduces GNI SSLB := by sorry end AMRangeAvoid.Characterization.Supplement
Source
Zeyong Li, STOC 2027 submission #502 (October 2026), Theorem 4.4, printed p.20 (PDF p.22); https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/502.pdf