Hacker News new | ask | show | jobs
by mdxn 4981 days ago
1. BPP <= P/poly was proven by L. Adleman.

2. I never said that P = BPP was hard to prove. I only brought up BPP because its derandomization, despite being limited to subexponential nondeterministic time, would still imply a lower bound of super polynomial circuit size (which could be the exponential lower bound presented by the author). The author is using this exponential lower bound (circuits) to immediately conclude that P != NP:

"The proof of Theorem 6.1 is now complete. We have: Corollary 6.5 P 6= NP"

Note: Theorem 6.1 is the lower bound