问题
3-色判定（ «图能否 3-染色 »）的精确指数复杂度：最好算法约 1.3289n（Beigel–Eppstein 2001 后的微幅改进）；猜想 «不能再快到 c < 1.328» 级—— «指数算法还能改进吗» 的样本问题。强指数时间假设（SETH）族预测下界、但 SETH 本身不可证（ «证明它 ⟹ 证 P≠NP 的指数版 »）。
主要概念
算法侧的机器
①分支化简： «高度点 » 先 «分支 »（ «染 A 或染 B»）， «低度结构 » 用 «多项式 » 处理；分支树的 «度量 »（ «度序列 »）分析给 c = 分支多项式的 «主根 »。②压缩： «3-色 ⟹ « 独立集 »» 链—— «3-色 ⟺ « 可 2-染 »的商»； «最大独立集 » 的 «1.2n» 级算法 «间接 » 供 «分支 » 用。③局部约减： «禁子结构 »（ «4-轮 » 型）的 «强制 » 消元—— «约减规则 » 的 «完备性 » 分析。
下界侧
SETH： «k-SAT 需要 (2−εk)n»； «3-色 SETH 版 »： «若 3-色在 1.3n，则 SAT 在 (2−δ)n»—— «归约 » 存在、 «SETH 本身 » 不可证（ «更接近 « 神谕 »»）。 «指数时间复杂度类 »（ETH、SETH、 «自然证明 » 障碍）的 «谱系 » 给 «下界 » 的 «结构化 » 表述。
主要命题与证明
命题 1（Beigel–Eppstein 上界骨架） 3-色判定 O(1.3289n)。
梗概 «分支 » 的 «两规则 »： «高次 »（度 ≥ 4）点 «三向分支 »（ «邻居的 « 色对 »» 归约）、 «低次 » 结构 «压缩 » 到 «独立集 » 子问题； «度量 » = « « 度 » 加权和 »， «分支多项式 » 的 «主根 » ≈ 1.3289。□
命题 2（SETH 归约） 3-色在 1.328n ⟹ k-SAT 的 «常数 » 提升（ «条件 » 下界： «不能太快 » 的 «可证 » 形式）。
进展与文献
Lawler 1976（ «3.46n» 首纪录）→ Beigel–Eppstein 2001（1.3289）→ 微幅改进（Kowalik、 «排序 » 优化）；Fomin–Kratsch《Exact Exponential Algorithms》教科书；Paturi–Pudlák–... 的 «SETH» 理论； «PCP 与指数 » 的 « hardness » 线。开放核心：1.3289 的 «机器极限 »（ «分支 » 范式的 «天花板 » 分析）与 «全新范式 » 的缺席； «着色 » 族的 «精确指数 » 图景（ «k-色 » 的 «ck» 谱）。