'從A到B'的直觀解釋是什麼？

Question

我現在正在研究複雜性理論，只是滿足'映射減少'。

我明白'從A到B的多項式時間約簡'爲'如果一個人可以求解B並且有多項式時間，那麼可以解答A. （對嗎？）

這意味着問題的不超過（含多項式時間）B.

那麼困難，應該是附近降低到B？我如何理解「減少」這個詞？

Answer 1

我們假設問題A是「要喝一杯咖啡」。有很多方法來解決這個問題，這取決於什麼你已經有：

• 進入你的車，去商店，買的咖啡，咖啡機和 杯的錯誤，得到家，電力新機器上，讓水，磨咖啡 等
• 買車，然後見上
• 獲取信用卡，去亞馬遜，找一個咖啡機，爲了它，找到 杯在家洗等。
• 申請信用卡，等待，然後看到上面
• 去星巴克，訂購咖啡，等待座位，等

在所有這些情況下，你已經減少您的問題已知的步驟（子問題）的序列。如果你知道，如何在合理的時間內解決這些子問題，並且他們的人數不是很大，那麼你可以在合理的時間內解決你的問題。

享受你的一杯咖啡！