「AからBへの削減」の直感的な説明は何ですか？

Question

私は現在、複雑さの理論を研究しており、「マッピングの削減」を満たすだけです。

「AからBへの多項式時間の短縮」は、「Bを解くことができ、多項式時間を持つことができれば、Aを解くことができます。 （私は右だ？）

これは、AがAからBに減少しているもの、そして、B.

（多項式時間で）よりも硬くない問題を暗示しますか？ 「削減」という言葉をどうすれば理解できますか？

Answer 1

問題Aは「コーヒーを飲む」としましょう。すでにを持っているものに依存し、この問題を解決するために多くの方法があります：

• 取得、カップを、あなたの車に入る店に行く、コーヒーのバグを買う、コーヒーマシンと 家庭、電源投入あなたの新しいマシンを、水を取得し、コーヒー を挽くなど
• 購入車、そして カップを見つけ、
の上には、順番に、コーヒーマシンを見つけ、アマゾンに行って、クレジットカードを見ます自宅で、それを洗うなど
• クレジットカードを申請し、待ってから上記を参照してください
• スターバックスに移動し、座席を待って、コーヒーを注文するなど

あなたはは、既知の手順（サブ問題）の順にあなたの問題を軽減したすべてのこれらのケースでは。あなたが知っている場合、どのように合理的な時間にこれらのサブ問題を解決すると、その数はあまりにも大きいではない、あなたは妥当な時間にあなたの問題を解決することができます。

コーヒーをお楽しみください！