fiercewindsの日記： P≠NPの聖杯を見つけた……

お久しぶりです。

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

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

証明のポイントは

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

です。APN関数がタイトルの「聖杯」ですね。

(F2拡大体の)APN関数とは、あるa∈F2拡大体について、
f(x+a)+f(x)=b, a(≠0),b ∈ F2拡大体
となるxが、各bについて高々2つ(x+a,x)しかない関数となります。
APN関数は差分解読法や線形解読法のような暗号解読法に強い暗号を構成するのに活用されている関数で、具体的な構成方法もいくつか開発されています。
（Wikipediaに載っていないマイナー技術ですが……）

APN関数の(a,b)は、上記で言うところの差分ベクトルそのものですので、APN関数を利用して問題を構成することでたくさんの差分ベクトルを含む問題を構成することができます。また、APN関数自体は高々PHの計算量で構成することができます。
よって、この結果からP≠NPを導くことができます。

下記に略証を示します。
簡単のため、問題の入力の構成するハミング空間はF2拡大体によるベクトル空間とします。
_____________________________________________________________________
定義１
「NNF回路族」を、（否定標準形のように）入力にのみNOT素子が繋がっている回路からなる回路族とする。（Sipser「計算理論の基礎」で述べられている通り）DTMを多項式規模の素子でエミュレートする回路族はNNF回路族に含まれる。

「隣の入力」を、ハミング距離で考えたときにその間に受理する入力が存在しない入力同士とする。

「間の入力」を、ハミング距離で考えたときに隣の入力の間にある拒否する入力とする。

「差分ベクトル」を、ハミング空間（F2拡大体）において、隣の入力を始終点とするベクトルとする。

「入力のある桁の差分ペア」を、入力素子の出力と入力素子に繋がる否定素子の出力の組とする。

「入力に対する回路の有効回路」を、ある入力に対して回路が1を出力するために必要な極小回路のうちのいずれか1つとする。

定理２
NNF回路において、全ての差分部分は有効回路のOR素子で合流する。

証明
ある入力の桁の差分ペアは(0,1)(1,0)のいずれかで、(1,1)となることはない。また、全ての有効回路に含まれる素子は、有効回路の単調性から1を出力し、最終的には出力素子に合流する。よって、NNF回路には差分ペア(0,1)(1,0)を合わせて出力するOR素子が存在する。□

定理３
NNF回路には、入力が少なくとも（対応する）差分ベクトルの始点・終点のどちらか片方を含む時のみに1になるAND素子が存在する。つまり、NNF回路は問題の差分ベクトル毎にAND素子が必要となる。

証明
定理２の通り、NNF回路では、全ての差分ペアがOR素子で合流する。合流の仕方は、NNF回路の単調性より、

1. 全ての差分ペアをAND素子で特定し、その結果をOR素子で合流する。
2. 差分ペアの一部をAND素子で特定し、その共通部分をOR素子で合流した後に、更にAND素子で特定する。

の2通りとなる。

(1)の場合、間の入力と隣の入力をAND素子で区別しなくてはならないため、いくつかのAND素子は入力が隣の入力の一部である時のみ1を出力する。つまり、このAND素子の出力は、入力が差分ベクトルの始点・終点を含むかどうかに対応しているため、定理の条件を満たす。

(2)の場合、NNF回路は間の入力を拒否しなくてはならないため、入力が間の入力の時、一部のOR素子の出力が0となる。つまり、有効回路が1を出力するのは、有効回路のOR素子が全て1を出力する時のみとなる。よって、有効回路が隣の入力で1となり間の入力で0となるためには、これらのOR素子が全て1のとき（すなわち入力が差分ベクトルの始点・終点を含む時）に1となり、いずれかのOR素子が0のとき（すなわち間の入力の時）に0を出力するAND素子が必要となる。

よって、全ての場合で定理が成り立つ。□

次に、差分ベクトルの個数を明確化する。そのために特別な問題「APNR」を定義する。

定義４
「APNR」を、入力w、入力長|w|、APN関数fにおける下記の判定問題とする。
w=uv, |u|=|v|, f(u)=v
ただしu,vはF2拡大体とする。

つまり、APNRはAPN関数fを入力に埋め込んだ問題となる。

定理５
APNR∈PH

証明（略証のみ示します）
F2拡大体における最小多項式gは高々定数回交替する交替TMで構成できるため、APN関数fも高々定数回交替する交替TMで計算できる。fからAPNRはDTMで高々多項式時間で計算できるので、定理が成り立つ□

定理６
APNRの差分ベクトルは2^(|u|-1)個存在する。

証明
wp = up vp
wq = uq vq
とすると、差分ベクトルは
wp + wq = (up + uq) (vp + vq)
= (up + uq) (f(up) + f(uq))
となる。
APN関数の定義より、
up + uq = a の時(f(up) + f(uq)) = b (a,b:定数)
となる(up, uq)は、（a,bにかかわらず）(up, uq)(uq, up)の2種類しか存在しない。

つまり(up, uq)の差分ベクトルup + uq = a が一致したとしても、up = uq + aの値により(f(up) + f(uq)) = bが異なる。つまり、(wp,wq)の差分ベクトルはupの値ごとに異なる。
これは、uの値ごとにwの差分ベクトルが存在することを意味するため、APNRの差分ベクトルは2^(|u|-1)個となる。□

_____________________________________________________________________
2018年05月09日に頂いたコメント(#3405474)

＞「隣の入力のペア毎に1つ以上のAND素子が必要」
「毎に」というのはなぜ？
その素子は他の入力では反応しないことが証明されるの？

すみません、「隣の入力のペア毎」というのは間違いですね。
実際、受理する入力が線形性を持つ場合、隣の入力は差分ベクトルの直和（直積）で表現することができますので、AND素子も隣の入力のペア毎には必要ありません。
上記の証明では「差分ベクトル毎にAND素子が必要」と修正しています。

真面目に読む気はないんだけれど

[Anonymous Coward]

>定理3
>NNF回路には、入力が少なくとも（対応する）差分ベクトルの始点・終点のどちらか片方を含む時のみに1になるAND素子が存在する。つまり、NNF回路は問題の差分ベクトル毎にAND素子が必要となる。

差分ベクトルの個数=そのようなAND素子の個数
という部分が証明できているようには全く見えないのですが。（思い込んでいるようには見えるけど。）

Pに属する問題であっても多項式規模の回路では解けないという証明になっちゃってませんか？

Re:真面目に読む気はないんだけれど

[fiercewinds (22740)]

コメントありがとうございます。
返事遅くなりすみません。

ご指摘の点、確かに証明が甘そうですね。
証明を厳密化してみます。