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

頂いた指摘事項を元に、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は同じ濃度のため、その論法は成り立たない。

/.Jの皆様にお知恵を拝借したいと思います。

私は趣味で数学を勉強しているのですが、計算機科学で重要な未解決問題と言われているP≠NP問題の解（らしきもの）を発見しました。

内容はそれほど難しくないのですが、本当にこれでいいか自信がちょっと持てません。学会でも発表してみたのですが、短時間＆参加者が少なかったため、あまり良いコメントはもらえませんでした。

お手数をお掛けしますが、/.Jの皆さんに下記の証明についてコメントいただけませんでしょうか？

__________________________________________
関数の出力の一意性より、ある集合Xの要素xについて、関数fの出力f(x)が集合Yに含まれて集合Xに含まれない場合は、XとYは等しくない。
∀X,Y,f(
　∀x∈X(f(x)∈Y)∧∃x∈X(f(x)∉X)
　→(X≠Y)
)

上記の式のX,YをP,NPに、fを論理演算子(¬,∨)に限定。
P≠NPとなる条件は、P問題のどちらかが真となる問題がNPに含まれる、Pの否定問題がPに含まれる、P問題のどちらかが真となる問題がPに含まれない、の3点
(∀p,q∈P(p∨qb∈NP))
∧(∀r∈P(¬r∈P))
∧(∃x,y∈P(x∨y∉P))
→(P≠NP)

第一の条件：チューリングマシンの構成より、P問題を計算する決定性チューリングマシンを複数まとめたものはP問題と同じリソースを使う非決定的チューリングマシンになる。よってNP問題となる。
∀p,q∈P(p∨q∈NP)

第二の条件：決定性チューリングマシンの構成より、P問題の真偽が逆のチューリングマシンはP問題と同じリソースを使う決定性チューリングマシンになる。よってP問題となる。
∀r∈P(¬r∈P)

第三の条件：背理法を用いて真であることを示す。P問題x,y,zの論理和x∨y及び否定¬zが全てPに含まれると仮定する。前述の結果∀z∈P(¬z∈P)を含めて考えと、P問題とその論理和・否定を組み合わせることによって任意の論理式を構成することができる。
この論理式と等価な回路からなる回路族の集合を考えると、この回路族の集合には決定問題に対応する回路族が含まれる（具体的な回路族が定まれば、P問題とその論理和・否定を組み合わせることによって構成することができる）。よってこの回路族の集合は決定問題Rと等しい。
つまり、仮定が正しければPとRは等しい。しかし、PはRを含まないため矛盾する。よって背理法よりx∨yにはP問題に含まれない問題が存在する。
(∀x,y∈P(x∨y∈P))∧(∀z∈P(¬z∈P))
→(P⊂R⊄P)=false
∴∃x,y∈P(x∨y∉P)

以上を組み合わせて、P≠NPが導出できる。
P≠NP

以上です。

当事者じゃないので簡単に。はてなが12月1日に予定している利用規約の改定についてのパブリックコメントの募集を行っています。 詳しくは真紀奈さんのところをご覧になってほしいのですが、今回の目玉は

第8条
4 本サービスの提供、利用促進及び本サービスの広告・宣伝の目的のために、当社はユーザーが著作権を保有する、本サービスへ送信された情報を無償かつ非独占的に本サイトに掲載することができるものとし、ユーザーはこれを許諾するものとします。この場合、ユーザーは当社に対して著作者人格権を行使しないものとします。

でしょうか。プライベートモードを使用しているかたはコメントしておいた方がいいと思います。
また、GPLなどの一部のライセンスでは混乱のもとになりやすい内容（サイトに掲載する際に、ライセンス条項などを改変／削除したものを掲載することができそう）ですので、なんらかのコメントを入れておいたほうが良いでしょう……まあ、GPLものをはてなにアップしている人はいないと思いますが。