【P≠NP予想】容疑者Ｘの献身を観たのですが

質問

容疑者Ｘの献身を観たのですが、

映画の一場面で「Ｐ≠ＮＰ問題」の話題が出てきました。

その中で、

「数学の問題について、自分で考えて答えを出すのと、他人から答えを聞いて、その答えが正しいかどうかを確認するのとではどちらが易しいか（難しいか）？
ただし、その問題には必ず答えが存在する。」 というセリフがありました。

恐らく、前者がクラスＰ、後者がクラスＮＰのことを表していると思われます。 しかし、「どちらが易しいか？（難しいか？）というのは、「Ｐ≠ＮＰ問題」の本質ではないような気がします。（Ｐの方がＮＰより解くのが大変ですよね・・）

Ｐ≠ＮＰ問題の核心部分は、「Ｐ⊂ＮＰが成り立つかどうか？（ＮＰ⊂Ｐは自明）」ではないでしょうか？

自分は映画を見ていて、「そんなの、他人から答えを聞いてその答えが正しいかどうかを確認する作業の方が、自分で答えを考え出すのより何百倍も簡単だろ！！」と思ってしまいました。

詳しい方解説お願いします！！！

回答No.3

graphaffine · ベストアンサー

>恐らく、前者がクラスＰ、後者がクラスＮＰのことを表していると思われます。 しかし、「どちらが易しいか？（難しいか？）というのは、「Ｐ≠ＮＰ
>問題」の本質ではないような気がします。（Ｐの方がＮＰより解くのが大変ですよね・・）

いいえ、一番本質的な部分です。
念のため注意しておきますが計算量理論（P≠NP予想もその範疇に含まれる）では、難しいとは質的な困難でなく手間がかかる（計算量が多い）と言う量的な困難のことを指します。
大雑把に言えば、P問題とは比較的やさしい問題、即ち100年ぐらい計算すれば終わるような問題、NP問題とは難しい問題、即ち宇宙が生まれてから消滅するまでを何回か繰り返すような時間のかかる問題です。
Ｐ≠ＮＰ問題は多分P vs NP問題と書くのが正確で、NP問題でもうまいやり方を見つければ100年で終わらせるようにできるのか、あるいはそれは不可能なのかのどちらかであるかを決定する問題です。で、タイトルにもあるように、後者であろうと予想されています。

お礼

ありがとうございます。

>>念のため注意しておきますが計算量理論（P≠NP予想もその範疇に含まれる）では、難しいとは質的な困難でなく手間がかかる（計算量が多い）と言う量的な困難のことを指します。
私はずっと勘違いしていました。この問題はどれくらいの「量」がかかるのかが争点なのですね。納得です。

もし、Ｐ≠ＮＰならば、ＮＰの方が難しく、
　　　Ｐ＝ＮＰならば、Ｐのほうが難しい、ということですね。

回答No.5

graphaffine

＞Ｐ≠ＮＰならば、ＮＰの方が難しく、
YES
＞Ｐ＝ＮＰならば、Ｐのほうが難しい、ということですね。
NO　　PとNPは同等になります。実際、Ｐ＝ＮＰですもの。

お礼

何度もすみません、ありがとうございます。

Ｐ＝ＮＰなら、ＰとＮＰは等価な問題の集合になるのですね。

回答No.4

Tacosan

本来的には, クラスP とかクラスNP とかいうのは「ある条件を満たすか満たさないかを答える」問題 (決定問題) に対して使う表現です. これだけ書いておいて, あとは大雑把に:
で, クラスP は「ノーヒントで」条件を満たすかどうかが答えられる問題, クラスNP は「ヒントを与えられれば」答えられる問題です.
ノーヒントで答えられるのであれば, ヒントを与えられても答えられますよね (ヒントを無視すればいい!). でも, ヒントが与えられれば答えられるからといって, ノーヒントで答えられるとは限りません.
だから P ⊂ NP は自明で, 逆が成り立つかどうかが年来の問題となっているわけです.
そこの表現でいえば NP は P に比べて「より易しいことしかできない」と考えられているわけです.

お礼

ありがとうございます。

>> NP は P に比べて「より易しいことしかできない」と考えられているわけです

このように表現されると少し納得できた気がします。頭が混乱してきたのでもっと勉強してきます！！！

回答No.2

koko_u_

>「そんなの、他人から答えを聞いてその答えが正しいかどうかを確認する作業の方が、
> 自分で答えを考え出すのより何百倍も簡単だろ！！」

「易しい」という言葉の定義が最も難しい点ですね。

一般的な意味では「他人から答えを聞いてその答えが正しいかどうかを確認する作業」も
一概に「易しい」とは言えません。
その証明に使われている道具立てすべてを理解しなければなりませんから。

適当な例が思いつきませんが
例えばフェルマーの大定理( x^n + y^n = z^n には非自明な解がない )について、
ひょっとしたら自分で「簡単な」証明を見出すことができるかもしれません。

その時、「自分で答えを考え出す」方が「易しかった」となるでしょう。
ワイルスがなした証明に穴がないことを理解するには楕円曲線などの「難しい」
数学的道具立てすべてを理解する必要があります。

お礼

ありがとうございます。。解法をたどる方が難しい場合がありそうですね・・。

でも、やはり、直感的には１から自分で見つけていく方が難しそうです。

回答No.1

rinkun

> Ｐ≠ＮＰ問題の核心部分は、「Ｐ⊂ＮＰが成り立つかどうか？（ＮＰ⊂Ｐは自明）」ではないでしょうか？
とりあえず包含関係は逆です。Ｐ⊂ＮＰは自明でＮＰ⊂Ｐが非自明。
Ｐは多項式時間で解ける問題。ＮＰは解が与えられたときに多項式時間で正解か確認できる問題。多項式時間で解ける問題は解が与えられたら当然多項式時間で確認できるので、Ｐ⊂ＮＰです。
ＮＰでありＰでない問題は（あるとすれば）自力では多項式時間で解けないが解を教えられれば（多項式時間で）解ける問題ということで、Ｐより難しいのです。
Ｐ＝ＮＰなら解を教えられるかどうかは多項式時間の枠では大きな差じゃないということで、Ｐ≠ＮＰは解を教えられるかどうかは多項式時間より大きな差だと言っているわけです。

お礼

訂正ありがとうございます。

ケースによっては、ＮＰの方が難しいのですね。もう少し、勉強します