OldNoviceWizardの日記: 長い旅路
PvsNPの証明がようやっとマトモなものになりそうなので帰って来た。
長かった……前回から2年弱か。内容も全然別物になったしなぁ。
まあ、PvsNPはあまり動きが無いのでぼちぼちやりますか。
OldNoviceWizardさんのトモダチの日記、みんなの日記も見てね。 アナウンス:スラドとOSDNは受け入れ先を募集中です。
PvsNPの証明がようやっとマトモなものになりそうなので帰って来た。
長かった……前回から2年弱か。内容も全然別物になったしなぁ。
まあ、PvsNPはあまり動きが無いのでぼちぼちやりますか。
前回の続き。
……今回も長かったなぁ。
結局、『直積となる部分を含まない真理値割当で真となる論理式』の構成が間違っていたので、arxiv.orgの論文の後半を差し替え。今度こそ合っていると良いな。
ただその過程で、周期&位相と計算複雑性に深い関係がありそうなことが見えてきたのは収穫。……まあ、判定問題の計算は周期関数の塊だから、ある意味当然だよね。もうちょっと周期関数について調べるとするか。
前回の続き。
前回ふにゃふにゃだった対称性について見直し。arxiv.orgの論文はアップロード中。
ようやっと帰ってこれた……結局、対称性だけじゃ上手く処理できなかったので、直積を使った独立性の切り口で再構成。しかし複雑になったなぁ。素直にベクトル空間で組んだ方が良かったかな?
その中で3^4/4^3=81/64というマジックナンバーが出て来た。調べてみるとピタゴラス音律(三分損益法)の長三度と同じものみたい。なんか繋がりがあったりするのかしらん。
前回の続き。
ということで、arxiv.orgの論文の内容を導出メインに変更。とりあえず蛇足の部分なので証明無しで演繹体系を位相空間として扱ったけど、こういった所は整理されていないのかしらん?
ついでに対称性の扱いで大穴が空いていたのでとりあえず塞ぐ。
これで2SATを条件から排除できる……はず。でもなんか証明がふにゃふにゃなんだよなぁ。
もうちょっと考えるか。
この前の続き。
証明の核となるTCNFがP完全だということを何とか証明できないかと悩んでいたら、呆気ない方法で完成した。
……まあ、例によって本当かどうか判らないけどね。
さっそくarxiv.orgの論文をアップデート。TCNFがP完全だとすると、超導出とかのややこしい手法を使わなくて良くなるから論文自体も簡素になるなぁ。
趣味で数学を勉強しているアマチュアです。
主にPvsNP問題にチャレンジしており、その周辺を勉強しております。
PvsNP問題にはカオスとか分散とか全体依存性とか色々と面白い特性があるのですが、そのあたりを整理して証明にチャレンジして見ました。
まあ、アマチュアなのでどこまで正しいのか判らない状態になってしまいましたが……
そこで、下記の証明にコメントを頂けませんでしょうか?
反証や反例など、間違っている証拠やギャップは大歓迎です。ここが曖昧とかここが変だとかの突っ込みも有り難いです。
ファイルはここにあります。
日本語はOther formatsの中ですね。
.tar.gzで保存されています。適当なツールで解凍して下さい。
____________________________________________________________________________________________________________
概要
本論文では位相の手法を用いてPとNPの違いを示す。CNFとHornCNFの位相的な構造の違いに着目し、CNFには多項式規模のHornCNFで記述できない論理式が存在することを示す。
まず始めに、CNFの記述的な面に着目した記述空間と、意味的な面に着目した意味空間を定義する。CNFはそれぞれの空間の連結部分集合の関係として定義する。また記述空間と意味空間はベクトル空間でもあるため、それぞれの空間においてCNFに対応する基底を構成することができる。特にHornCNFは、真理値割当の集合と節が変数を介して一対一に対応するという制約を持つ。
次に、CNFをHornCNFに変換する具体的な方法としてTCNFを定義する。HornCNFを還元したTCNFは高々多項式規模だが、CNFを還元したTCNFは多項式規模に納まらない。またTCNFはHornCNFでもあるため、結果としてCNFはHornCNFに多項式規模では還元できないことがわかる。
私は悩みをリストアップし始めたが、そのあまりの長さにいやけがさし、何も考えないことにした。-- Robert C. Pike