One-Way-Function
最壞情況單向功能
最壞情況的單向函式定義如下
$$ \forall A \exists x : pr(A(f(x))\in f^{-1}(f(x)))\neq 1 $$ 你能舉出這種功能的任何例子嗎？
當且僅當 P ≠ NP 時才存在最壞情況的單向函式，因此，如果我是你，我不希望很快得到你問題的明確答案:)。
另一方面，如果你願意假設 P ≠ NP，那麼構造這樣的函式並不難（這實際上正好是我在上一段中陳述的定理的一半證明）。