P=NPと仮定したときの計算

Question

計算時間についての話です．
P=NPと仮定したとき，NPに属する任意の問題はNP困難といえますでしょうか．

Comments

[1T2R3M4]

https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q13236941058

以下ご対応ください。
https://teratail.com/help#posted-otherservice

[grape_ll]

友人と一緒に考えていて，友人がそちらのサイトで質問を投稿したみたいなのですが，その場合でもリンクを張るべきでしょうか．

Answer 1

仮定云々と関係せず、言えません。反例として、「足し算の結果が正しいか検算する」問題を挙げておきます。

• この問題は「YesかNoかで答えが出る」かつ「多項式時間で結果が出る」のでP問題であり、「多項式時間での検証ができる」以上NP問題でもあります。
• 他のNP完全問題をこの問題へ還元することはできません。つまり、「NP困難ではない」問題です。

Comments

[grape_ll]

確かにそのようですね，例も分かりやすく，理解できました．
ありがとうございます．