引用ethan_g · 2017-08
“Other one, by Mathias Hauptmann, is here: On Alternation and the Union Theorem”
补充 Hauptmann 另一篇声称证明 P != NP 的论文
证明 P=Σ₂^p 的假设会自相矛盾,因而该假设不成立
在假设 P=Σ₂^p 下,证明 McCreight 与 Meyer 并集定理针对 Σ₂^p 类的一个新变体,得到一个满足 P=DTIME(F)=Σ₂(F)=Σ₂^p 的并集函数 F。同时证明 Gupta 关于 DTIME(t)⊊Σ₂(t) 结果的一个变体,并证明这两个结果相互矛盾,因此假设 P=Σ₂^p 不能成立。
有评论者在汇总各种声称证明 P≠NP 的论文时提到它,并指出其状态不明。
“Other one, by Mathias Hauptmann, is here: On Alternation and the Union Theorem”