“P不等於NP”與“單向函式的存在”的關係

我們知道，如果存在單向函式，則 P≠NP。為什麼我們不能得出結論，如果 P ≠ NP，那麼存在單向函式？是否有一個多項式時間可計算函式在最壞的情況下難以反轉並且不是單向的？

為什麼我們不能得出結論，如果 P ≠ NP，那麼存在單向函式？

因為到目前為止還沒有人能夠證明這一說法，請參見此處。

語句“如果單向函式存在，那麼 $ P \neq NP $ " 是一種暗示，它只是一種方式。如果我們建立對立面，我們會得到 “如果 $ P = NP $ ，則單向函式不存在”。

在邏輯謬誤列表中，我們可以找到：

• 肯定結果，這基本上只是建立逆向（轉身暗示的方向）。
• 否定前件，這正好是蘊涵兩邊的逆。

這些是（或多或少）關於邏輯的常見錯誤，只有對立式不會改變陳述的實際含義。單獨的反轉和轉換都不能保留含義 - 因此如果您想證明一個陳述，則它們是無效的。

是否有一個多項式時間可計算函式在最壞的情況下難以反轉並且不是單向的

任何 NP 完全搜尋問題都會為您提供一個候選者。這正是 NP 類和單向函式中的搜尋問題之間的區別：前者是針對最壞情況定義的，而後者是針對平均情況定義的。這也是為什麼 NP 完全問題在密碼學中不太有趣的原因，在密碼學中，如果問題的最壞情況是困難的，這可能是不夠的。

引用自：https://crypto.stackexchange.com/questions/45171