按年被提到
20162016 · 2 次2026
数学、逻辑与理论›数学猜想与重大证明·arXiv:1602.04781 · cs.CC

On Alternation and the Union Theorem

论交替与并集定理
Mathias Hauptmann · 2016

证明 P=Σ₂^p 的假设会自相矛盾,因而该假设不成立

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 3 人首次 2016-06-12 · 最近 2017-08-14
3不同的人
3活跃月份
3讨论串
2被引(OpenAlex)

在假设 P=Σ₂^p 下,证明 McCreight 与 Meyer 并集定理针对 Σ₂^p 类的一个新变体,得到一个满足 P=DTIME(F)=Σ₂(F)=Σ₂^p 的并集函数 F。同时证明 Gupta 关于 DTIME(t)⊊Σ₂(t) 结果的一个变体,并证明这两个结果相互矛盾,因此假设 P=Σ₂^p 不能成立。

HN 为什么提它

有评论者在汇总各种声称证明 P≠NP 的论文时提到它,并指出其状态不明。

其他难度 5 / 5约 60 分钟经得起时间
读之前最好知道
1计算复杂性理论
2多项式层次(polynomial hierarchy)
3McCreight-Meyer 并集定理
4交替图灵机

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用ethan_g · 2017-08

“Other one, by Mathias Hauptmann, is here: On Alternation and the Union Theorem”

补充 Hauptmann 另一篇声称证明 P != NP 的论文
A Solution of the P versus NP Problem?原评论 ↗
被提交为 story · 2 次