fiercewindsの日記： 【ご意見募集】P≠PHの証明（P≠NPの証明） 10
P≠PHの証明ですが、一部気になるところがありましたので補足しました。
本質的な部分の修正はありません。
引き続き、ギャップがありそうな部分や理解の難しい部分が
ありましたら、ご指摘いただけると助かります。
_____________________________________________________________________
○概要
本証明では、問題の入力それぞれの関係に着目することで、多項式階層(PH)に属する問題がPに属する問題よりも複雑であることを示しています。
Sipser「計算理論の基礎」に証明がありますが、（否定標準形のように）入力に繋がる素子を除いてNOT素子を使わない「ほとんど単調な回路族」は、決定性チューリングマシン(DTM)を（実行時間の）多項式個数の素子でエミュレートすることができます。この「ほとんど単調な回路族」は回路の構成に強い制限があるため、問題の複雑性を容易に明確化できます。
この「ほとんど単調な回路族」はAND素子とOR素子の回路となり、
a)受理する入力同士で、それぞれ異なる値の部分はOR素子で繋がる
b)受理する複数の入力の間に他の受理する入力が無いときは、（間違えて拒否すべき間の入力を受理しないように）受理する入力を特定するAND素子が存在する
という特徴を持ちます。つまり、「ほとんど単調な回路族」は、受理する入力のペアとその間にある拒否する入力を区別するために、受理する値のペア（あるいは受理する値そのもの）のみで1を出力して間の値で0を出力するAND素子を持たなくてはなりません。
次に、上記の隣同士の入力のペアが多数ある「隣人問題」はどのようなものなのかを考えます。具体的な問題として選言標準形(DNF)による恒真式のうち、ある変数の肯定否定を全て入れ替えたときのみ恒真で、一部のみ入れ替えたときは恒真とならない式を判定する問題を考えます。このような恒真式は恒真式判定問題を神託とするcoNP神託機械で計算可能なためPHに属します。また、このような恒真式は、任意の恒真式から構成可能で、またある恒真式から多項式規模を超える「隣同士の入力」のペアを構成することが出来ます。
上記の２つの結果
「ほとんど単調な回路族」は隣同士の入力を判定するために固有のAND素子が必要
入力長の多項式規模を超える隣同士のペアを持つ「隣人問題」が存在
より、「ほとんど単調な回路族」はいくつかの「隣人問題」を多項式個数の素子では計算できません。また、「隣人問題」には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通り構成することができる。
もしも上記変換により同じ節からなる入力になる、あるいは入力がNTDにならない場合は、定理８、９の証明の手順を用いて、a)b)が異なる節からなるNTDになるように修正する。
※なお、証明の簡略化のため、簡約によって入力の長さが短くなった場合は、埋め草で同じ長さになるように調整するものとする。
定理８、９より、上記の変数の置換はそれぞれの変数ごとに行うことができ、また変数の置換において肯定否定の置き方をa)b)どちらにするかは任意に選択することができる。また置換できる変数も対数規模の個数に収まらないため、上記の手順で作成するNTDの濃度もまた多項式規模に収まらない。
また、変数の置換を行った後のNTDは、変換した後の変数yについて、式に含まれる変数yの肯定否定を全て置換したNTD
y,¬y -> ¬y,y
もまたNTDとなる。定理５より、yの肯定否定を置換したNTDと元のNTDはそれぞれ隣の入力となるため、隣の入力のペアの濃度もまた多項式規模に収まらない。□
定理１３
NTDを計算するNNF回路族の素子数は多項式規模に収まらない。
証明
定理１２より、NTDにある隣の入力のペアの濃度は多項式規模に収まらない。よって定理３より、NTDを計算するNNF回路族の素子数もまた多項式規模に収まらない。
定理１４
PはPHを含まない。
証明
Sipser「計算理論の基礎」の通り、NNF回路族はDTMを実行時間の多項式規模の素子数でエミュレートすることができる。しかし、定理１３より、NNF回路族はNDTを多項式規模の素子数で計算することが出来ないため、NTDはPに含まれない。また定理１０よりNTDはPHに含まれる。よって、PHはPではない。
確認ですが (スコア:1)
おっしゃりたいことは
NTD を導入すると P ⊂ NTD ⊆ PH となる，だから P != PH ってことですか？
でもそれは NTD を導入したからであって
NTD以外のアルゴリズム，つまり理想的な アルゴリズム X が見つかれば
P = X = PH
となりませんか？
証明すべきはそのような X が存在しないことでは無いでしょうか？
多くの人はそのようなXは存在しないと信じてますが，
存在しないことを証明するのが P != NP のキモだと思います．
Re:確認ですが (スコア:1)
コメントありがとうございます。
> NTD を導入すると P ⊂ NTD ⊆ PH となる，だから P != PH ってことですか？
いいえ。問題のクラスで表すと
PH ∋ NTD ∉ P
--> P != PH
ですね。
定義１(とSipserの証明)より
P ⊂ 入力長の多項式規模のNNF回路族で計算できる問題のクラス
定理１３より
NTD ∉ 入力長の多項式規模のNNF回路族で計算できる問題のクラス
定理１０より
NTD ∈ PH
から、定理１４にて
・定義１、定理１３より
NTD ∉ P
・定理１０より
NTD ∈ PH
よって
PH ∋ NTD ∉ P
--> P != PH
を導いています。
Re:確認ですが (スコア:1)
たとえば
NTD ∉ P
を
x(NTD) ∈ P
と変換する x() が存在するとどうなるでしょうか？
個人的には，そんなx()は存在しないと思いますが，
その存在を議論することが自体が P!=NP の問だと思います
Re:確認ですが (スコア:1)
そのようなxは存在しますが、多項式時間還元にはなりません。
多項式時間還元でx(NTD) ∈ Pとなるxが存在する
-->（x(NTD) ∈ Pより）入力長の多項式規模のNNF回路族でx(NTD)が計算できる。
-->（xが多項式時間還元となることより）入力長の多項式規模のNNF回路族でNTDが計算できる。
となり、定理１３と矛盾します。
Re: (スコア:0)
「定理１３と矛盾する」とおっしゃっていますが
それは「NTDを計算するNNF回路族の素子数は多項式規模に収まらない。」と決め込んでいるからではありませんか？
これは正しくは「今の所，多項式規模還元する方法が見つかっていないだけ」だと思います．
Re:確認ですが (スコア:1)
この部分が本証明の肝となります。
定理３より、
NNF回路族には（隣の入力のペアの）差分部分のどちらか片方を含む時のみに1になるAND素子が存在。
−＞隣の入力のペア毎に1つ以上のAND素子が必要。（さもなければ間の入力を区別できない）
定理１２（及び定理５、８、９、１１）より、
NTDに含まれる隣の入力のペアの濃度は、入力長に対して多項式規模に収まらない。
よって、NTDを計算するNNF回路族の素子数は多項式規模に収まりません。
Re: (スコア:0)
肝というか，DTMをエミュレートしているので自明だと思うのですが…
Re:確認ですが (スコア:1)
肝というのは、
「隣の入力のペア毎に1つ以上のAND素子が必要」
「NTDに含まれる隣の入力のペアの濃度は、入力長に対して多項式規模に収まらない」
−＞「NTDを計算するNNF回路族の(AND)素子数は多項式規模に収まらない」
の部分です。
上記は、DTMをエミュレートしているからと言って自明ではありません。
いつまでたっても後出し、後出し。 (スコア:0)
ああいうと、実はこれで。
こういうと、これはあれで。
Re: (スコア:0)
＞「隣の入力のペア毎に1つ以上のAND素子が必要」
「毎に」というのはなぜ？
その素子は他の入力では反応しないことが証明されるの？