fiercewindsの日記： P≠NP 4
前回の日記から2年近く経ちましたが、P≠NPの証明をアップデートしました。
NP問題が独立するP問題の無限集合という考え方をより精密にするため、「具象化DTM」と言う特別なDTM(の無限集合)を定義しています。また、具象化DTMの独立性を計算量に落とし込むために、回路族の「極小回路」という部分回路も導入しています。
具体的な回路を使うことで、証明もイメージしやすくなったかと思います。
○概要
NP問題とP問題の違いを、回路族の構造の違いから証明する。
問題を計算する回路族の入力には、回路の構造として表される対称性が存在する。この対称性を明確化するために「極小回路」と呼ぶ部分回路を定義する。極小回路はある入力を計算するのに必要な素子のみを残した部分回路のうちのいずれか一つであり、入力によってそれぞれ異なる。
他方、NP問題を計算するNTMの入力にも、非決定遷移関数で示される対称性が存在する。この対称性を明確化するために、「具象化DTM」と呼ぶDTMを定義する。具象化DTMはNTMの非決定遷移をあらかじめ定められた順番iで（決定的に）実行するDTMで、NTMの非決定遷移のうちの一つに対応するDTMとなる。
ここでPとNPの違いを明確化するために、SAT問題を回路族で計算することを考える。
SAT問題の具象化DTMにはpを真理値割当とする回路値計算問題(CVPp)を用いる。この回路族は全てのCVPpに対応する極小回路を含む必要があり、またそれぞれのCVPpの極小回路は他のCVPq≠pに含まれない独自の素子を持つ。CVPpの数は入力長に対して多項式規模に収まらないため、SAT問題を計算する回路族も多項式規模に収まらず、結果として P ≠ NPとなる。
○詳細
定義１
回路 C において、ある入力 x の「極小回路」 c = [C(x)] を、
「素子の出力を反転しても回路の出力が変化しない素子を全て削除した部分回路」
とする。(なお、残った素子間の配線は削除しないものとする)
また、入力素子から出力素子に繋がる一連の配線と素子を回路経路と呼ぶ。
定理２
もし回路Cqが[Cp(x)]の全ての回路経路を含むのならば、[Cq(x)]は[Cp(x)]に等しい。
証明
極小回路の定義より、[Cp(x)]の回路経路全体には[Cp(x)]にある素子全てが含まれる。
よって、条件よりCqは[Cp(x)]の全ての素子（と配線）を含む。
ここで[Cq(x)]を考えると、極小回路の定義よりCqから[Cp(x)]以外の素子を取り除いた部分回路になるため、[Cp(x)]=[Cq(x)]となる。
定義３
あるNTMに対する「具象化DTM」Diを、
「NTMの非決定遷移関数をあらかじめ定められた順番iで（決定的に）実行するDTM」
とする。
同様に、SATに対する具象化DTMとなる回路値計算問題CVPiを
「SATの入力に対して、変数の真理値割当をiとして回路値計算を行うDTM」
とする。
また、CVPpについて、fix(p)を
「CVPp(fix(p))=1, CVPq≠p(fix(p))=0となる入力のうちいずれか一つ」
fix(0)を
「SAT(fix(0))=0となる入力のうちいずれか一つ」
とする。
定理４
全てのCVPpには対応するfix(p)が存在する。
証明
明らかに、fix(p)=fix(0)∨pと等価な入力は
CVPp(fix(0)∨p)=1, CVPq≠p(fix(0)∨p)=0
となるため、定理は成り立つ。
定理５
SATを計算する回路族[SAT]は、全ての[CVPp(fix(p))]を含む。
証明
[SAT](fix(p))=1が正しいのならば、[SAT](fix(p))から[CVPp(fix(p))]を構成することができる。
よって定理が成り立つ。
定理６
全て[CVPp(fix(p))]は他の[CVPq≠p(fix(q))]には無い独自の回路経路と素子を含む。
証明
背理法で証明する。
CVPq≠pの全ての回路をC-q、[CVPq(fix(q))]の全ての回路を[C-q]とし、[C-q]が[CVPp(fix(p))]の全ての回路経路を含むと仮定する。
C-qは[C-q]を含むことより、定理２から
[C-q(fix(p))]=[CVPp(fix(p))]
となる。
しかし、定義３、定理４より
[C-q(fix(p))](fix(p))=C-q(fix(p))=0
[CVPp(fix(p))](fix(p))=CVPp(fix(p))=1
となるため矛盾する。
よって定理が成り立つ。
定理７
[SAT]は多項式規模に収まらない。
証明
定理６の通り、[SAT]に含まれる全ての[CVPp(fix(p))]は独自の回路経路と素子を持つ。また、pは入力長に対して対数規模に収まらないため、[CVPp(fix(p))]の個数は入力長に対して多項式規模に収まらない。
よって、[SAT]もまた多項式規模に収まらない。
系８
P≠NP
最後 (スコア:0)
最後の、定理7から系8を導くところは自明ではないと思います。
ある問題AがPに属することと、
その問題Aを解く回路族[C]の回路経路の数が多項式規模に収まることが、
必要十分条件であることの証明が必要に思います。
＃論理式「CVPq≠p(fix(p))=0」のパースが厳しいです。
＃「q≠pとなる任意のqについてCVPq(fix(p))=0」の意味でしょうか。
Re:最後 (スコア:1)
コメントありがとうございます。
配線は全て元の回路のままですので、極小回路に独自の回路経路があれば、その回路経路上に独自の素子も存在します。
ですので、独自の回路経路が多項式規模に収まらなければ素子も多項式規模に収まらないことになります。
ただ、そちらではなくて定理６に間違いがありそうなので、ちょっと深堀しようかと思います。
Re: (スコア:0)
極小回路などの概念を正しく読み取れているかはわかりませんが
回路経路は独自でも、独自の素子があるとは限らないのではないでしょうか。
回路上の分岐と合流を単純化したものとして、以下のような回路を考えます。
x1
／ ＼
x2 x3
＼ ／
x4
／ ＼
x5 x6
＼ ／
x7
このとき、ある割当p1～p4についてのそれぞれの極小回路の独自回路経路が、もしも仮に
p1: x1→x2→x4→x5→x7
p2: x1→x3→x4→x5→x7
p3: x1→x2→x4→x6→x7
p4: x1→x3→x4→x6→x7
のようになった場合、
各回路経路は異なっていてそれぞれ独自であるものの、素子には独自のものは無い、
ということにならないでしょうか。
Re:最後 (スコア:1)
ふむ、グラフとしては経路のパターンが4種類ありますね。
確かに証明が足りなさそうです。
ざっと考えてみましたが、下記の方針でギャップを埋められそうです。
このグラフはあくまで回路であることに注意すると、(x1が出力側だとして)x7の出力が0,1の2通りしか無いため、取りうる回路経路の組み合わせも2通りのみ。
出力の種類を増やすには配線と素子を追加する必要があるので、結果として独自の素子が必要となる。
ただ、やはり証明６に間違いがありましたので、そちらのほうが痛いですね……もっと回路の構造に踏み込む必要がありそうです。