Fortnow 用相关性界证明 Almost-ParityP=BP·ParityP,给出 Toda 定理新证法
fortnow · x · 2026-09-29
计算复杂度学者 Lance Fortnow 发布 6 页 arXiv 论文，利用 Chattopadhyay、Hatami、Lee、Lovett、Tal、Viola 近期的指数级相关性界（关于 F₂ 多项式与 majority 的 XOR 之间），证明 Almost-ParityP = BP·ParityP：即在随机预言机下几乎必然属于 ParityP^R 的语言类等于 BP·⊕P。
- 这是 Bennett-Gill 的 Almost-P = BPP 与 Nisan-Wigderson 的 Almost-PH = PH 结论在 parity 情形上的类比。
- 关键技术：一个多项式种子长度的伪随机生成器，能在指数多个变量上 fool 多项式度的 F₂ 多项式。
- 应用：给出 Toda 定理前半部分 PH ⊆ BP·⊕P 的随机预言机式简化证明（沿 Regan-Royer 思路），逐层应用 Valiant-Vazirani 与 Papadimitriou-Zachos 归约，无需让概率量词穿过预言机。
「研究」频道最新
- 6 个可视化 AI 学习资源：从 Transformer 到扩散模型都能拆开看 — techNmak · 2026-09-29
- 18 万条工具调用决策数据集开源，可训练小模型替代 LLM 做路由 — MaziyarPanahi · 2026-09-29
- Pruned CTC 内存降5.1倍,让LLM词表直接做语音识别 — X-LANCE · 2026-09-29
- SCOPD:剪枝仅留10%视觉token,VLM仍保92%性能 — uoft · 2026-09-29
- AnswerMap:免训练黑盒方法让VLM空间解释AUC达0.85 — Mohamed Eltahir · 2026-09-29
- 学者称「AI 署名」定义模糊,学术会议分流政策一两年内将失效 — ipeirotis · 2026-09-29