Hacker News Reader

Not sure if I'm labouring under basic misconception here (or if you're trolling). First, you note that BPP <= P/poly. Secondly, you note that it is hard to prove P = BPP, but this is not necessary, all we need is the trivial P <= BPP. Then P <= P/poly < NP (if the author is correct).

View on HN

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

Reply on news.ycombinator.com