お久しぶりです。

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素子が必要」と修正しています。

みなさん、こんばんは。

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

なおチューリングマシンをエミュレートする回路の説明はGoogle bookにあるIntroduction to the Theory of Computationの383ページ以降(Theorem 9.30)に載っています。一部しか載っていないので、vixraに「計算理論の基礎」をベースにまとめた証明を投稿しました。

単調回路は(PARITYやCLIQUEといった)重要な発見がいくつかありますので、この「ほとんど単調な回路族」も過去に研究した論文があってもおかしくはないのですが、Webで検索した範囲では見つけられませんでした。
＃否定素子数限定の研究はあるんですけどね……
Wikipediaでも、Circuit complexityに「計算理論の基礎」Theorem 9.30の結果だけ書かれていて、「ほとんど単調な回路族」についての言及はありません。

vixraのpaperにも書きましたが、「ほとんど単調な回路族」は
　受理する入力と拒否する入力の(ハミング空間の)サンドイッチ構造は、
　「ほとんど単調な回路」のそれぞれ異なる(個別の)素子に対応する
という重要な性質を持っているようです。
この回路族の研究や論文がWebで見つからないのは何か理由があるのか、あるいは単に自分の調べ方が悪いのか……と思い、皆さんに聞いてみようと考えました。

もしご存知の方がいらっしゃいましたら、コメントいただけると助かります。

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ではない。

コメントありがとうございます。
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通り構成することができる。
※なお、証明の簡略化のため、簡約によって入力の長さが短くなった場合は、埋め草で同じ長さになるように調整するものとする。
定理８、９より、上記の変数の置換はそれぞれの変数ごとに行うことができ、また変数の置換において肯定否定の置き方を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ではない。

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の証明にギャップがあったのでアップデートしました。
回路族を使用するのは前回と同様ですが、今回はSipser「計算理論の基礎」にある「決定性チューリングマシンをエミュレートする、ほとんど単調な回路族」を使用することでギャップを埋め、かつ証明を具体的に考えることができるようにしています。
また、NPだと条件を満たす問題の設定が難しかったため、多項式階層(PH)をPから分離しています。

証明の概要は下記の通りです。

○概要
今回は、問題の入力それぞれの関係に着目して、多項式階層(PH)に属する問題の複雑性を示しています。

Sipser「計算理論の基礎」に証明がありますが、決定性チューリングマシン(DTM)を（実行時間の）多項式個数の素子でエミュレートする回路族は、入力に繋がる素子を除いてNOT素子を使わない「ほとんど単調な回路族」となっています。この「ほとんど単調な回路族」は回路の構成に強い制限があるため、この回路族を使うことで問題の複雑性を明確化しやすくなります。

この「ほとんど単調な回路族」はAND素子とOR素子のDAG回路となり、
a)受理する入力同士で、それぞれ異なる値の部分はOR素子で繋がる
b)受理する複数の入力の間に他の受理する入力が無いときは、（間違えて拒否すべき間の入力を受理しないように）a)のOR素子が全て1であることを判定する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回路は差分部分の間の入力を拒否しなくてはならないため、入力が間の入力のときは一部のOR素子の出力が0となる。つまり、有効回路が1を出力するのは、有効回路のOR素子が全て1を出力する時のみとなる。よって、有効回路が隣の入力で1となり間の入力で0となるためには、これらのOR素子が全て1のとき（すなわち入力が差分部分を含む時）に1となり、いずれかのOR素子が0のとき（すなわち差分部分の間の入力の時）に0を出力するAND素子が必要となる。

次に、隣の入力の個数を明確化する。そのために特別な問題「隣人問題」を定義する。

定義４
「隣人問題」(NTD)を、極小の恒真式となる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の条件を満たす。よって定理が成り立つ。

定理７
任意のNTDは、全ての変数の組み合わせをいずれかの節に含むNTDに変換することができる。

証明
fが変数x,yを含む節を持たない場合、下記の手順で変数x,yを含む節を持つNTD gを構成することができる。
1)x,¬xを含む節にy,¬yのいずれかを追加し、f'とする。
2)f'が恒真式でない場合、f'で0となる真理値割当で1となる新しい（単数又は複数の）節をf'に追加し、gとする。

定理８
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の証明をアップデートしました。
前回の証明だと色々とギャップが残っていましたので、証明や定義を修正して埋めています。前回指摘頂いた回路経路についても、証明の修正で不要になったため削除しました。
独自の概念が減ったので、内容が把握しやすくなったかと思います。

●概要
NP問題とP問題の違いを、回路族の構造から証明する。

P問題を計算する回路族の入力には、回路の構造として表される対称性が存在する。この対称性を明確化するために「有効回路」と呼ぶ部分回路を定義する。有効回路はある入力を計算するのに必要な素子のみを残した部分回路（のうちのいずれか一つ）であり、入力によってそれぞれ異なる回路となる。

他方、NP問題を計算するNTMの入力にも、非決定遷移関数で示される対称性が存在する。この対称性を明確化するために、「具象化DTM」と呼ぶDTMを定義する。具象化DTMは、iで示される順番で（決定的に）NTMの非決定遷移を実行するDTMで、NTMの非決定遷移のうちの一つに対応するDTMとなる。

ここでPとNPの違いを明確化するために、SAT問題を回路族で計算することを考える。
SAT問題の具象化DTMには、iを真理値割当とする回路値計算問題(CVPi)を用いる。SAT問題の回路族は全てのCVPiに対応する有効回路を含む必要があり、またそれぞれのCVPiの有効回路は他のCVPI≠iに含まれない独自の素子を持つ。CVPiの数は入力長に対して多項式規模に収まらないため、SAT問題を計算する回路族も多項式規模に収まらない。つまり、P≠NPとなる。

●詳細

○定義１
回路 C において、ある入力 x の「有効回路」 c = [C(x)] を、
「素子の出力を反転しても回路の出力が変化しない素子を全て削除した部分回路」
とする。
また、有効回路の集合を有効回路族とする。
なお簡単のため、ここで扱う回路族は一様回路族とする。

○定義２
NTMに対する「具象化DTM」を、
「NTMの非決定遷移関数を、iで示される順番で（決定的に）実行するDTM」
とする。

同様に、SATに対する具象化DTMとして、「回路値計算問題」「CVPi」を
「SATの入力に対して、変数の真理値割当をi={0,1}^*として計算するDTM」
「CVPI」を
「CVPI = ∨CVPi | i∈I」
とする。
ただし、簡単のためiの桁が足りなくなった場合は0を代用するものとする。また、桁が余った場合は常に0を出力するものとする。

「[SAT]」をSATに対応する回路族、「[CVPi]」をCVPi=1→[CVPi]=1となる有効回路族、「[CVPI]」をCVPI=1 → [CVPI]=1となる有効回路族とする。

○定理３
∀I,i(I∌i → ∃x((|x|＜O(|i|)) ∧ (CVPI(x)=0) ∧ (CVPi(x)=1)))

証明
論理式の構成より明らかに、x(t)≡(t=i)かつ|x|＜O(|i|)となる論理式xが存在する。よって定理を満たす入力xが存在する。

○定理４
∀I,x(CVPI(x)=1 → [CVPI](x)=1)
∀I,x([CVPI](x)=0 → CVPI(x)=0)

証明
定義より明らかなため証明は省略する。

○定理５
∀I,i,x([CVPI]⊇[CVPi] → ([CVPi](x)=1 → [CVPI](x)=1))

証明
[CVPi]の定義より、もしも[CVPi](x)=1ならば、[CVPI]＼[CVPi]のどの素子を[CVPi](x)に追加しても回路の値は変わらない。よって[CVPI](x)=1となる。

○定理６
∀I,i,x([CVPI]⊇[CVPi(x)] → ([CVPI](x)=0 → [CVPi](x)=0))

証明
背理法を用いる。定理の否定
∃I,i,x([CVPI]⊇[CVPi(x)] ∧ [CVPI](x)=0 ∧ [CVPi](x)=1)
を仮定する。
定理５
∀I,i,x([CVPI]⊇[CVPi] → ([CVPi](x)=1 → [CVPI](x)=1))
→∀I,i,x([CVPI]⊇[CVPi(x)] → ([CVPi(x)](x)=1 → [CVPI](x)=1))
→∀I,i,x([CVPI]⊇[CVPi(x)] → ([CVPi](x)=1 → [CVPI](x)=1))
より、
∃I,i,x([CVPI]⊇[CVPi(x)] ∧ [CVPI](x)=0 ∧ [CVPi](x)=1)
→∃I,i,x(([CVPi](x)=1 → [CVPI](x)=1) ∧ [CVPI](x)=0 ∧ [CVPi](x)=1)
→∃I,i,x([CVPI](x)=1 ∧ [CVPI](x)=0 ∧ [CVPi](x)=1)
となり矛盾する。
よって定理は成り立つ

○定理７
∀I,i(I∌i → ∃x((|x|＜O(|i|)) ∧ ¬([CVPI]⊇[CVPi(x)]))

証明
背理法で証明する。定理の否定
∃I,i((I∌i)∧∀x(|x|＜O(|i|) → [CVPI]⊇[CVPi(x)]))
を仮定する。

定理３
∀I,i(I∌i → ∃x((|x|＜O(|i|)) ∧ (CVPI(x)=0) ∧ (CVPi(x)=1)))
より、
∃I,i((I∌i)∧∀x(|x|＜O(|i|) → [CVPI]⊇[CVPi(x)]))
→∃I,i(F1∧∀y(|y|＜O(|i|) → [CVPI]⊇[CVPi(y)]))
    F1 = ∃x((|x|＜O(|i|)) ∧ (CVPI(x)=0) ∧ (CVPi(x)=1))
→∃I,i,x((|x|＜O(|i|))∧(CVPI(x)=0)∧(CVPi(x)=1)∧([CVPI]⊇[CVPi(x)]))

また定理６
∀I,i,x([CVPI]⊇[CVPi(x)] → ([CVPI](x)=0 → [CVPi](x)=0))
より、
∃I,i,x((|x|＜O(|i|))∧(CVPI(x)=0)∧(CVPi(x)=1)∧([CVPI]⊇[CVPi(x)]))
→∃I,i,x((|x|＜O(|i|))∧(CVPI(x)=0)∧(CVPi(x)=1)∧([CVPI](x)=0→[CVPi](x)=0))

また定理４
∀I,x(CVPI(x)=1 → [CVPI](x)=1)
∀I,x([CVPI](x)=0 → CVPI(x)=0)
より
∃I,i,x((|x|＜O(|i|))∧(CVPI(x)=0)∧(CVPi(x)=1)∧([CVPI](x)=0→[CVPi](x)=0))
→∃I,i,x((|x|＜O(|i|))∧(CVPI(x)=0)∧([CVPI](x)=1)∧(CVPI(x)=0→[CVPi](x)=0))
→∃I,i,x((|x|＜O(|i|))∧(CVPI(x)=0)∧([CVPI](x)=1)∧([CVPi](x)=0))
となり矛盾する。
よって定理は成り立つ

○定理８
[SAT]は多項式規模に収まらない。

証明
定理７の通り、全ての[CVPi]には他の[CVPI]に含まれない独自の素子が存在する。この素子は|i|のたかだか多項式規模の入力xを計算するのに必要となる。また、[CVPi]は|i|に対して指数規模となり、|x|の多項式規模に収まらない。よって、[CVPi]に対応する独自の素子の数は|x|に対して多項式規模に収まらず、[SAT]もまた多項式規模に収まらない。

○系９
P≠NP

前回の日記から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

定義の明記が必要というコメントがあったので、プレプリントを晒しておきますね。

英語が下手というのは脇に置いておいていただければ……

反応無いなぁ。
明確なギャップが無いのでコメントしづらい、というのだったら良いんだけど。