パスワードを忘れた? アカウント作成

こちらは、fiercewindsさんのユーザページですよ。 みんなの日記はここから一覧を見ることができます。

13608727 journal
数学

fiercewindsの日記: P≠NPの聖杯を見つけた…… 2

日記 by fiercewinds

お久しぶりです。

P≠NP問題ですが、引き続きサーベイしていたところ具合の良い関数を見つけたので、証明をアップデートしました。
これで、ほぼ既存技術の組み合わせでP≠NPの証明ができました。
検証済みの技術を使用していますので、信頼性も随分上がったかと思います。
ギャップもほぼ埋まった感じです。

また、2018年05月09日に頂いたコメント(#3405474)ですが、元コメントには返信できなくなっているのでこちらで回答します。文末を確認ください。
ご指摘のポイントは確かに間違いになりそうな部分を含んでいましたので、現在の証明では修正しています。(隣の入力のペアよりも、隣の入力の差分ベクトルが問題の本質でした)

証明のポイントは

  • 「(DTMを模倣できる)ほとんど単調な回路」で計算する場合、受理する入力の差分ベクトル毎にAND素子が必要になる。
  • F2拡大体上の非線形な関数として「準完全非線形関数(APN関数)」が存在し、その差分ベクトルの個数は入力長の指数規模になる。
13559993 journal
数学

fiercewindsの日記: 【どなたか知りませんか?】ほとんど単調な回路の論文

日記 by fiercewinds

みなさん、こんばんは。

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

13551266 comment

fiercewindsのコメント: Re:確認ですが (スコア 1) 10

肝というのは、
「隣の入力のペア毎に1つ以上のAND素子が必要」
「NTDに含まれる隣の入力のペアの濃度は、入力長に対して多項式規模に収まらない」
−>「NTDを計算するNNF回路族の(AND)素子数は多項式規模に収まらない」
の部分です。

上記は、DTMをエミュレートしているからと言って自明ではありません。

13550873 comment

fiercewindsのコメント: Re:確認ですが (スコア 1) 10

この部分が本証明の肝となります。

定理3より、
NNF回路族には(隣の入力のペアの)差分部分のどちらか片方を含む時のみに1になるAND素子が存在。
−>隣の入力のペア毎に1つ以上のAND素子が必要。(さもなければ間の入力を区別できない)

定理12(及び定理5、8、9、11)より、
NTDに含まれる隣の入力のペアの濃度は、入力長に対して多項式規模に収まらない。

よって、NTDを計算するNNF回路族の素子数は多項式規模に収まりません。

13548478 comment

fiercewindsのコメント: Re:確認ですが (スコア 1) 10

そのようなxは存在しますが、多項式時間還元にはなりません。

多項式時間還元でx(NTD) ∈ Pとなるxが存在する
-->(x(NTD) ∈ Pより)入力長の多項式規模のNNF回路族でx(NTD)が計算できる。
-->(xが多項式時間還元となることより)入力長の多項式規模のNNF回路族でNTDが計算できる。
となり、定理13と矛盾します。

13548278 comment

fiercewindsのコメント: Re:確認ですが (スコア 1) 10

コメントありがとうございます。

> NTD を導入すると P ⊂ NTD ⊆ PH となる,だから P != PH ってことですか?

いいえ。問題のクラスで表すと
PH ∋ NTD ∉ P
--> P != PH
ですね。

定義1(とSipserの証明)より
P ⊂ 入力長の多項式規模のNNF回路族で計算できる問題のクラス

定理13より
NTD ∉ 入力長の多項式規模のNNF回路族で計算できる問題のクラス

定理10より
NTD ∈ PH

から、定理14にて
・定義1、定理13より
 NTD ∉ P
・定理10より
 NTD ∈ PH
よって
PH ∋ NTD ∉ P
--> P != PH
を導いています。

13547743 journal
数学

fiercewindsの日記: 【ご意見募集】P≠PHの証明(P≠NPの証明) 10

日記 by fiercewinds

P≠PHの証明ですが、一部気になるところがありましたので補足しました。
本質的な部分の修正はありません。

引き続き、ギャップがありそうな部分や理解の難しい部分が
ありましたら、ご指摘いただけると助かります。

_____________________________________________________________________
○概要
本証明では、問題の入力それぞれの関係に着目することで、多項式階層(PH)に属する問題がPに属する問題よりも複雑であることを示しています。

13547079 journal
数学

fiercewindsの日記: 【ご意見募集】P≠PHの証明(P≠NPの証明)

日記 by fiercewinds

コメントありがとうございます。
P≠PHの証明、昨日ご指摘頂いた内容を修正しました。

引き続き、ギャップがありそうな部分や理解の難しい部分が
ありましたら、ご指摘いただけると助かります。

_____________________________________________________________________
○概要
本証明では、問題の入力それぞれの関係に着目することで、多項式階層(PH)に属する問題がPに属する問題よりも複雑であることを示しています。

13546724 comment

fiercewindsのコメント: Re:素朴な疑問 (スコア 1) 4

以前にスラドに投稿したときに色々と意見をもらえたので、
今回も投稿してみました。

Paperはまとめていますので、今回コメント頂いたらその内容を
反映してECCC辺りに投稿しようかと思います。
#大きなギャップが無ければですが……

typodupeerror

※ただしPHPを除く -- あるAdmin

読み込み中...