On Use of an Explicit Congruence Predicate in Bounded Arithmetic - yoriyukiの日記

プレプリントをArXivにアップした→[0904.0335] On Use of an Explicit Congruence Predicate in Bounded ArithmeticP≠NPを証明する構想の第一ステップになる予定。構想とは次のようなものだ。P≠NPを示すのに、PやNPを特徴付ける論理体系を考え、それらが異なっていることを示す。特徴付けるとは、その体系で計算の停止性が言えるプログラムの計算量がちょうどPやNPになっているもので、いろいろな体系があるがBussによるPを特徴付けるとNPを特徴付けるが有名だ。からP=NPが言える。またからP≠NPは示せると信じられている*1。そこで、P≠NPを示す代わりにを示すことにチャレンジする。さて、論理体系が異なっていることを示す常套手段はゲーデルの不完全性定理だ。ある体系Tの無矛盾性がSで言えればS≠Tであることが言える。しかし、

[kururu_goedel]

期待age

[yhara]

"P≠NPを証明する構想の第一ステップになる予定。" < このフレーズかっこよすぎる