fiercewinds 曰く、
/.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
以上です。