fiercewindsの日記： 【ご意見募集】P≠NPの証明（P≠PHの証明） 4
3/7のP≠PHの証明を若干強化しましたのでアップします。
自分で調べた限りでは、致命的なギャップを見つけることはできませんでした。
もしもギャップがありそうでしたらご指摘いただけると助かります。
また、理解の難しい部分があるようでしたら、その部分もご指摘ください。
証明の説明を簡単に出来ないか検討しようかと思います。
なお、3/7からの主な修正箇所は、
・定理３の証明のケースを追加して、証明を厳密化。
・NTDの存在を厳密化するために定理７、９を追加
となります。
また、いくつかの用語について、Wikipediaへのリンクを追加しました。
基本的な考え方は3/7版と同様で、ポイントは
・問題の「入力同士の関係」を用いて、問題の複雑性を測定する。
・「入力同士の関係」を測定するために、Sipser「計算理論の基礎」にある「決定性チューリングマシンをエミュレートするほとんど単調な回路族」を用いる。
となります。
上記は計算複雑性理論でもあまり使われていない手法かと思いますが、この手法を使うことで、問題の構造をより厳密＆簡単に扱うことができるようになりました。
証明の概要は下記の通りです。
○概要
本証明では、問題の入力それぞれの関係に着目することで、多項式階層(PH)に属する問題がPに属する問題よりも複雑であることを示しています。
Sipser「計算理論の基礎」に証明がありますが、決定性チューリングマシン(DTM)を（実行時間の）多項式個数の素子でエミュレートする回路族は、入力に繋がる素子を除いてNOT素子を使わない「ほとんど単調な回路族」となっています。この「ほとんど単調な回路族」は回路の構成に強い制限があるため、問題の複雑性を容易に明確化できます。
この「ほとんど単調な回路族」はAND素子とOR素子の回路となり、
a)受理する入力同士で、それぞれ異なる値の部分はOR素子で繋がる
b)受理する複数の入力の間に他の受理する入力が無いときは、（間違えて拒否すべき間の入力を受理しないように）異なる値をその値に特定するAND素子が存在する
という特徴を持ちます。つまり、「ほとんど単調な回路族」は、間に受理する入力を持たない入力のペアを判定するために、その値のみを受理して間の値を拒否するための固有のAND素子を持たなくてはなりません。
このような隣同士の入力がたくさんある「隣人問題」を考えます。本証明では、選言標準形(DNF)による恒真式のうち、ある変数の肯定否定を全て入れ替えたときのみ恒真で、一部のみ入れ替えたときは恒真とならない式を判定する問題を考えます。このような恒真式は恒真式判定問題をオラクルとする非決定性チューリングマシンの否定で計算可能なためPHに属します。また、このような恒真式は、任意の恒真式から構成可能で、またある恒真式から多項式規模を超える「隣同士の入力」のペアを構成することが出来ます。
上記の２つの結果より、上記の「隣人問題」は入力長に対して多項式規模を超えるペアを持つ問題が存在し、かつ「ほとんど単調な回路族」はそれぞれの隣同士の入力を判定するために固有の素子が必要となります。つまり、「ほとんど単調な回路族」は「隣人問題」を多項式個数の素子では計算できません。また、「隣人問題」にはPHに属する問題も存在することと、「ほとんど単調な回路族」は多項式個数の素子で多項式時間のDTMをエミュレートできる（多項式個数でPが計算できる）ことから、PHはPに含まれないことがわかります。
○詳細
定義１
「NNF回路族」を、（否定標準形のように）入力にのみNOT素子が繋がっている回路からなる回路族とする。（Sipser「計算理論の基礎」で述べられている通り）DTMをエミュレートする回路族はNNF回路族に含まれる。
「隣の入力」を、ハミング距離で考えたときにその間に受理する入力が存在しない入力同士とする。
「間の入力」を、ハミング距離で考えたときに隣の入力の間にある拒否する入力とする。
「隣の入力の差分部分」を、隣の入力と互いに異なる部分とする。
「隣の入力の一致部分」を、隣の入力と互いに一致する部分とする。
「入力に対する回路の有効回路」を、ある入力に対して回路が1を出力するために必要な極小回路のうちのいずれか1つとする。
定理２
NNF回路において、全ての差分部分は有効回路のOR素子で合流する。
証明
差分部分が同じ入力に現れることはないため、差分部分で1を出力する有効回路のうち一部の素子は、他方の差分入力で必ず0となる。また、全ての有効回路に含まれる素子は1を出力し、最終的には出力素子に合流する。よって、NNF回路は0と1を出力する素子を何処かで合流させなくてはならない。
よってこれらの差分部分はOR素子で合流する。□
定理３
NNF回路には、入力が少なくとも（対応する）差分部分のどちらか片方を含む時のみに1になるAND素子が存在する。
証明
定理２の通り、NNF回路では、全ての差分部分がOR素子で合流する。合流の仕方は、NNF回路の単調性より、
a)全ての差分部分をAND素子で特定し、その結果をOR素子で合流する。
b)差分部分の一部をAND素子で特定し、その共通部分をOR素子で合流した後に更にAND素子で特定する。
の2通りとなる。
a)の場合、他の間の入力と差分部分をAND素子で区別しなくてはならないため、いくつかのAND素子は入力が差分部分である時のみ1を出力する。このAND素子の出力は入力が差分部分を含むかどうかに対応しているため定理の条件を満たす。
b)の場合、NNF回路は差分部分の間の入力を拒否しなくてはならないため、入力が間の入力の時、一部のOR素子の出力が0となる。つまり、有効回路が1を出力するのは、有効回路のOR素子が全て1を出力する時のみとなる。よって、有効回路が隣の入力で1となり間の入力で0となるためには、これらのOR素子が全て1のとき（すなわち入力が差分部分を含む時）に1となり、いずれかのOR素子が0のとき（すなわち差分部分の間の入力の時）に0を出力するAND素子が必要となる。
よって、全ての場合で定理が成り立つ。□
次に、隣の入力の個数を明確化する。そのために特別な問題「隣人問題」を定義する。
定義４
「選言標準形(DNF)恒真式による隣人問題」(NTD)を、極小の恒真式となる選言標準形(DNF)のうち、あるリテラルの肯定否定を入れ替えた式が恒真式となり、リテラルの真の部分集合の肯定否定を入れ替えた式が恒真式とならないDNFを判定する問題とする。
なお極小の恒真式となるDNFとは、どの節を削除しても恒真を維持できない恒真のDNFとする。
定理５
f∈NTDならば、fのある変数xのリテラルx,¬xを入れ替えた式gはfの隣の入力となる。
証明
恒真式がリテラルx,¬xの置換に関して対称であることから、g∈NTDは明らか。
また、f,gの間の入力はリテラルx,¬xの真の部分集合の肯定否定を入れ替えた式であるため、NTDの定義から恒真式にならず、NTDに含まれない。よってf,gの間にはNTDで受理する入力は存在せず、f,gは隣の入力となる。□
定理６
極小の恒真式に対応するNTDが存在する。
証明
実際に極小の恒真式 fからNTDを構成する。
もしfがNTDでないのならば、fには真の部分集合の肯定否定を入れ替えても恒真式となる変数xが存在する。そのような変数xは、その真の部分集合を自由変数yに置き換えたとしても恒真式となる。
上記の自由変数yを含む恒真式についても、もし真の部分集合の肯定否定を入れ替えても恒真式となる変数が存在するときは、上記の操作を繰り返すことができる。この操作を行うごとに間の恒真式は減少するため、この操作は必ず終了する。その終了したときの恒真式はNTDの条件を満たす。よって定理が成り立つ。□
定理７
下記の条件を満たす3リテラルDNF fが存在する。
a)与えられた任意の値の組み合わせTにおいて、f(t)=1|t∈T となる。
b)それぞれのDNFの節に含まれる3つの変数はどのような組み合わせも取りうることができる（任意の変数の組み合わせで成り立つ）。ただし、それぞれの変数のリテラルの肯定否定はf毎に決めることができる。
c)fの長さは、fに含まれる変数の種類のたかだか多項式規模で収まる。
証明
fに含まれる節を
f = c1∨c2∨…∨cn
とし、fに含まれる変数を
x1,x2,…,xk
とする。またc1をx1,x2,x3からなる節とする。
この場合、c1が取り得るリテラルの組み合わせは下記の8通りとなる。
x1∧x2∧x3,¬x1∧x2∧x3,x1∧¬x2∧x3,
¬x1∧¬x2∧x3,x1∧x2∧¬x3,¬x1∧x2∧¬x3,
x1∧¬x2∧¬x3,¬x1∧¬x2∧¬x3,
これらの可能なリテラルの組み合わせは、取り得る値の組み合わせを8分割にする。よつていずれかのリテラルの組み合わせは値の組み合わせTの少なくとも1/8の個数の値にて1となる。よって、適切なリテラルの組み合わせをc1にすることで、f(t)=1としなくてはならないt∈Tの個数を7/8に減らすことができる。
上記の手順は、c1だけではなくc2,…,cnそれぞれで行うことができ、それぞれの節でTの個数を7/8ずつ（少なくとも1つ以上）減らしていくことができる。ここで、Tの個数はfに含まれる変数の数kから高々2^kのため、nの多項式規模n^dで全てのTをカバーすることができる。よって、定理の通り変数の多項式規模の節（任意の変数から構成される）で、任意の値の組み合わせで1となるDNF fを構成することができる。□
定理８
任意のNTDは、全ての変数の組み合わせをいずれかの節に含むNTDに変換することができる。
証明
fが変数x,yを含む節を持たない場合、下記の手順で変数x,yを含む節を持つNTD gを構成することができる。
1)x,¬xを含む節にy,¬yのいずれかを追加し、f'とする。
2)f'が恒真式でない場合、f'で0となる真理値割当で1となる新しい（単数又は複数の）節をf'に追加し、gとする。□
定理９
任意のNTDは、どのリテラルx,¬xを入れ替えても、同じ節の構成にならない（x,¬xの置換に対して節の構成が対称でない）NTDに変換することができる。
証明
上記定理８の証明で用いた手順を修正することで、定理９のNTDを構成する手順とすることができる。
上記証明の2)において、追加する節の変数の組み合わせを、式に含まれるどの変数とも異なる組み合わせにすることで、節に含まれるリテラルの肯定否定を入れ替えても同じになる節が存在しないようにすることができる。よって定理が成り立つ。□
定理１０
NTDはPHに属する。
証明
NTDは次のステップにより計算することができる。
a)入力がDNFの恒真式であることを判定する。
b)変数の真の部分集合全ての組み合わせについて、その肯定否定を変換した式が恒真式で無いことを判定する。
ここでb)は変数の真の部分集合を全称的に選択して恒真式で無いことを判定することで計算することができるので、この計算は恒真式判定問題を神託とするcoNP神託機械で計算することができる。よってNTDはPHに属する。□
定理１１
もしもNTDの入力pが変数x,yを含む節を持つ場合、変数yを変数xに変換した（そして全てのx∧xをxに、全てのx∧¬xを0に簡約してどの変数を変換したかがわからないようにした）入力qもまたNTDになる。
証明
背理法で証明する。定理の否定
NTDの入力pには、変数x,yを含む節を持ち、かつyをxに変換した入力qがNTDにならない入力pが存在する。
を仮定する。
入力pは恒真式となるため、変数yをxに置き換えた入力qもまた恒真式となる。また恒真式におけるxと¬xの対称性より、入力qのxと¬xを置換した式もまた恒真式となる。
よって、qがNTDにならないという仮定より、qにあるxの真の部分集合の肯定否定を入れ替えた式q'が恒真式になる必要がある。
また、pがNTDであることより、pが恒真式となるのはa)全てのxの肯定否定を入れ替えた場合かb)全てのyの肯定否定を入れ替えた場合のどちらかとなる。よって、qもまた元からあったxの肯定否定を入れ替えるか、yから変換したxの肯定否定を入れ替えるかのどちらかの場合のみ恒真式となる。このことは、yをxに変換した後にx∧xやx∧¬xの簡約が起こらない、つまりx,yは同じ節に含まれないことを意味する。
しかし、仮定よりpにはx,yを含む節を持つため、この結果は矛盾する。
よって背理法より定理が成り立つ。□
定理１２
NTDの濃度は入力長に対して多項式規模に収まらない。
証明
定理１１より、いくつかのNTDからは同じ節に含まれる変数を置換することによって新たなNTDを構成することができる。変数の置換は、1つの変数につき
a) y,¬y -> x,¬x
b) y,¬y -> ¬x,x
の2通り構成することができる。
※なお、証明の簡略化のため、簡約によって入力の長さが短くなった場合は、埋め草で同じ長さになるように調整するものとする。
定理８、９より、上記の変数の置換はそれぞれの変数ごとに行うことができ、また変数の置換において肯定否定の置き方をa)b)どちらにするかは任意に選択することができる。また置換できる変数も対数規模の個数に収まらないため、NTDの濃度もまた多項式規模に収まらない。□
定理１３
NTDを計算するNNF回路族の素子数は多項式規模に収まらない。
証明
定理３より、NNF回路族は隣の入力を間の入力と区別するために、隣の入力ごとに固有の素子を必要とする。定理５より、NTDのある入力とその入力のある変数の肯定否定を入れ替えた入力のペアはお互い隣の入力となり、定理１２より、NTDの濃度は多項式規模に収まらない。よって、NTDを計算するNNF回路族の素子数は多項式規模に収まらない。
定理１４
PはPHを含まない。
証明
Sipser「計算理論の基礎」の通り、NNF回路族はDTMを実行時間の多項式規模の素子数でエミュレートすることができる。しかし、定理１３より、NNF回路族はNDTを多項式規模の素子数で計算することが出来ないため、NTDはPに含まれない。また定理１０よりNTDはPHに含まれる。よって、PHはPではない。
暗にP≠NPを前提としてませんか？ (スコア:0)
たとえば
> NTDの濃度は多項式規模に収まらない。よって、NTDを計算するNNF回路族の素子数は多項式規模に収まらない。
ここの「よって、」は P≠NPを仮定してませんか？
Re:暗にP≠NPを前提としてませんか？ (スコア:1)
ご指摘ありがとうございます。
ここはちょっと修正＆補足が必要そうです。
まず「NTDの濃度は多項式規模に収まらない」の部分ですが、正確には
「NTDにある隣の入力のペアの濃度は多項式規模に収まらない」
ですね。定理１２もそれに合わせて
定理１２
NTDに含まれる隣の入力のペアの濃度は、入力長に対して多項式規模に収まらない。
に修正した方が良さそうですね……
また、「よって」の部分ですが、
定理３：
NNF回路には、入力が少なくとも（対応する）差分部分のどちらか片方を
含む時のみに1になるAND素子が存在する。
−＞NTDのそれぞれの隣の入力毎に、（受理すべき隣の入力の差分部分全体と
拒否すべき間の入力を判別するために）入力がその差分部分全体を含むかどうかを
判定する独自のAND素子を持つ必要がある。
を前提とする「よって」になります。
定理３自体はP≠NPを仮定していませんので、この「よって」もP≠NPを
仮定していません。
後で説明の補強を考えることにします。
＃単純に「定理３より」のような説明を追加する感じですかね。
素朴な疑問 (スコア:0)
なぜarXivでやらないのですか？
ここに書いても、専門家の目に触れることはほとんど無いと思いますが。
Re:素朴な疑問 (スコア:1)
以前にスラドに投稿したときに色々と意見をもらえたので、
今回も投稿してみました。
Paperはまとめていますので、今回コメント頂いたらその内容を
反映してECCC辺りに投稿しようかと思います。
＃大きなギャップが無ければですが……