Astra 证明 n^1/400 近似硬度,或催生基于 P≠NP 的密码学
thomasahle · x · 2026-09-03
推主在讨论中提到,Astra 还证明了基于 3-SAT 的 n^(1/400) 近似硬度。这一结果可用于构造在假设 P≠NP 前提下安全的密码学方案,那仍然很有价值。
他还指出:要做出类似结论"只需"证明某问题是 Exp 难的——即使 P=NP 这也可能成立,但难度更大。目前最好的无条件电路下界是 Astra 对 permanent 的 n⁴/log n 结果。
「研究」频道最新
- Cohere 发布 ATE 数据集:近70万 MCP 工具透视 agent 自动化趋势 — Cohere_Labs · 2026-09-03
- 研究显示在线 RL 中动作分块同样显著提升 Contrastive RL 表现 — ben_eysenbach · 2026-09-03
- 编码模型数据枯竭？PL 学者提出「意图计算」新范式破局 — LingmingZhang · 2026-09-03
- davidad 力挺:无约束 RLVR 简单奖励函数应被全面禁用 — davidad · 2026-09-03
- Computerphile 深入讲解 AI 水印原理并现场演示实现 — Computerphile · 2026-09-03
- TrafficLab 3D：仅需监控 mp4 + 谷歌地图位置即可生成 3D 数字孪生交通可视化 — tom_doerr · 2026-09-03