/.Jに聞け：【助けて】 P≠NPの証明、これで合ってる？（第二回）

fiercewinds 曰く、

先日はコメントありがとうございました。

頂いた指摘事項を元に、P≠NPの証明をアップデートしました。
また、反論とその回答も追加しています。

引き続きコメントいただければと思います。

_____________________________________________________________
○条件(使用する公理)

• ZFC
• 計算モデルはチューリングマシン(TM)とする。
  証明の簡単化のため等価な回路族も使用する。
• 複雑性クラスは集合とする。
• 漸近的解析は複雑性クラスの分離のみ成立する。
  つまり、時間・空間階層定理は成立するが、
  ∀x,y∈P(x∨y∈P)|P:複雑性クラス
  が成り立つとは限らない。

_____________________________________________________________
○証明

・定理1
(∀p,q∈P(p∨q∈NP))∧(∃x,y∈P(x∨y∉P))
→(P≠NP)

証明
関数の出力の一意性より明らかなため省略する。


・定理2
∀p,q∈P(p∨q∈NP)

証明
TMの構成より、P問題を計算する決定性TMを複数まとめたものはP問題と同じ計算資源を使う非決定的TMになる。よってNP問題となる。


・定理3
(∀r∈P(¬r∈P))→(∃x,y∈P(x∨y∉P))

証明
背理法を用いて証明する。
¬(∀r∈P(¬r∈P))→(∃x,y∈P(x∨y∉P))
= (∀r∈P(¬r∈P))∧(∀x,y∈P(x∨y∈P))
と仮定する。

簡単のためTMと等価な回路族を使用する。

Pは、回路族の各回路の射影関数
Pp(n,k)(w)=
{入力長がnの場合、k文字目の値を出力する
{入力長がn以外の場合、偽の値を出力する
Pn(n,k)(w)=
{入力長がnの場合、k文字目の値の否定を出力する
{入力長がn以外の場合、偽の値を出力する
を含む。

よって、
Pp(n,k)(w)∈P
Pn(n,k)(w)∈P
(∀r∈P(¬r∈P))∧(∀x,y∈P(x∨y∈P))
であり、これは回路族の再帰的定義と一致する。

よってPは回路族全体と等しく、P=Rが成立する。
しかし、時間階層定理よりP≠Rであり、P=Rと矛盾する。

したがって、背理法より
(∀r∈P(¬r∈P))→(∃x,y∈P(x∨y∉P))
が成立する。


・定理4
∀r∈P(¬r∈P)

証明
決定性TMの構成より、P問題の真偽が逆のTMはP問題と同じ計算資源を使う決定性TMになる。よってP問題となる。


・定理5
(∃x,y∈P(x∨y∉P))

証明
定理3、4より明らかである。


・定理6
P≠NP

証明
定理1、2、5より明らかである。

以上で証明は完了しました。

_____________________________________________________________
○反論とその回答

反論1
複雑性クラスでは定数倍の計算資源増加は無視するから、∀x,y∈P(x∨y∈P)とならないのはおかしい。

回答
本証明では、通常の計算複雑性理論から「漸近的解析で同じ複雑性となる複雑性クラスは同じクラスになる」という公理を外しているため、定数倍の計算資源増加を無視できるかどうかは定まっていない。
上記の通り、この公理無しで∃x,y∈P(x∨y∉P)が証明出来ているため、漸近的解析を根拠に∀x,y∈P(x∨y∈P)とすると計算モデルと矛盾する。


反論2
この証明の系としてPSPACE≠NPSPACEとなるが、これはSAVITCHの定理と矛盾している。

回答
SAVITCHの定理は、漸近的解析を用いて定数倍の計算資源増加を無視しているため、PSPACE≠NPSPACEとなる。
SAVITCHの定理も、正確には
　NSPACE(f(n)) ⊂ SPACE(f^2(n))
のため、定数倍の計算資源増加を無視しなければPSPACE≠NPSPACEとならないかもしれない。


反論3
定理3において背理法の仮定からP=Rを導いているが、問題の無限個の論理和を用意しない限りこのような結論にならないはずだ。

回答
背理法にて∀x,y∈P(x∨y∈P)と仮定することにより、（本来ならばありえない）問題の無限個の論理和を仮定の中で実現している。


反論4
定理3において、証明にありえない条件（問題の無限個の論理和を含む問題）を使用しているから、証明になっていない。

回答
問題の無限個の論理和はあくまで背理法の仮定の中で発生する。背理法によりこの仮定は否定されるため、Pの中には問題の無限個の論理和を含む問題は存在しない


反論5
有理数と無理数の関係（有理数の有限和は有理数のまま）を考えると、問題の無限個の論理和を含む問題を実際に構成しない限りはこの証明は成り立たないはずだ。

回答
有理数と無理数は濃度が異なるが、PとNPは同じ濃度のため、その論法は成り立たない。