One-Way-Function
隨機電路是否可能計算單向函式？
我記得在某處讀到過（在某些合理的假設下）隨機選擇的具有許多輸入和輸出（現在假設相等）的布爾電路將是一個具有高機率的單向函式。這是真的？
你記得的說法好得令人難以置信。目前尚不清楚（因為問題 P ?= NP 仍然是開放的）是否存在單向函式。如果你記得的斷言是真的，那將證明單向函式的存在。
PS 雖然 P = NP 排除了單向函式的存在，但即使 P != NP 單向函式的存在仍然是一個懸而未決的問題。