xmldtp https://blog.hatena.ne.jp/xmldtp/ ウィリアムのいたずらの、まちあるき、たべあるきーPART2 https://xmldtp.hatenadiary.org/ Weblog 素朴な疑問。思いつきなんで、たぶん、間違ってると思うけど・・・ まず、Ｐ≠ＮＰのＰとは、判定問題のうち、ある決定性チューリング機械によって多項式時間で解かれるものの全体（Ｗｉｋｉｐｅｄｉａより引用）、つまり言い換えると、これがきたら、つぎにやるのはこれ、と（決定的に）決まっている状態で、対象が増えれば、処理時間が増えていくもの。つまり、シリアル処理ですな（いや、シリアルって、たべものじゃないよ、シスコみたいな・・って、なおさら混乱しそうだ ^^;) それに対して、ＮＰは、非決定性チューリングマシンによって多項式時間で解くことができる問題なんだけど、出てきた答えは、本当に正しいかどうかを多項式時… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fxmldtp.hatenadiary.org%2Fentry%2F652decc52f8d7b21f819f3da3d14a899" title="Ｐ≠ＮＰのＮＰって、本当に計算難しいの？ - ウィリアムのいたずらの、まちあるき、たべあるきーPART2" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2009-07-14 11:30:49 rich https://xmldtp.hatenadiary.org/entry/652decc52f8d7b21f819f3da3d14a899 1.0 100%