お久しぶりです。

P≠NP問題ですが、引き続きサーベイしていたところ具合の良い関数を見つけたので、証明をアップデートしました。
これで、ほぼ既存技術の組み合わせでP≠NPの証明ができました。
検証済みの技術を使用していますので、信頼性も随分上がったかと思います。
ギャップもほぼ埋まった感じです。

また、2018年05月09日に頂いたコメント(#3405474)ですが、元コメントには返信できなくなっているのでこちらで回答します。文末を確認ください。
ご指摘のポイントは確かに間違いになりそうな部分を含んでいましたので、現在の証明では修正しています。（隣の入力のペアよりも、隣の入力の差分ベクトルが問題の本質でした）

証明のポイントは

• 「(DTMを模倣できる)ほとんど単調な回路」で計算する場合、受理する入力の差分ベクトル毎にAND素子が必要になる。
• F2拡大体上の非線形な関数として「準完全非線形関数（APN関数）」が存在し、その差分ベクトルの個数は入力長の指数規模になる。

みなさん、こんばんは。

もしご存知の方がいらっしゃいましたらお教えください。
M.Sipser「計算理論の基礎」にある、チューリングマシンをエミュレートする「ほとんど単調な回路族」について研究している論文などはありませんでしょうか？

P≠PHの証明ですが、一部気になるところがありましたので補足しました。
本質的な部分の修正はありません。

引き続き、ギャップがありそうな部分や理解の難しい部分が
ありましたら、ご指摘いただけると助かります。

_____________________________________________________________________
○概要
本証明では、問題の入力それぞれの関係に着目することで、多項式階層(PH)に属する問題がPに属する問題よりも複雑であることを示しています。

コメントありがとうございます。
P≠PHの証明、昨日ご指摘頂いた内容を修正しました。

引き続き、ギャップがありそうな部分や理解の難しい部分が
ありましたら、ご指摘いただけると助かります。

_____________________________________________________________________
○概要
本証明では、問題の入力それぞれの関係に着目することで、多項式階層(PH)に属する問題がPに属する問題よりも複雑であることを示しています。