色编码技巧突破：对称布尔函数获深度-3 小电路

计算复杂度理论出现出人意料的新结果：借助组合数学中的 Alon-Yuster-Zwick 色编码技巧，每个对称布尔函数都可以用大小为 2^{O(√n)} 的深度-3 电路表示，突破了原有认识。Ryan Williams 补充背景称，他在多篇论文中反复使用过该技巧，约两年前也曾尝试类似构造来证明这一结论，但因放弃太早而与该成果失之交臂。

2026-09-30 ~ 2026-09-30 · 2 条相关