Proving Lower Bounds Via Pseudo-random Generators

摘要

In this paper, we formalize two stepwise approaches, based on pseudo-random generators, for proving P ≠ NP and its arithmetic analog: Permanent requires superpolynomial sized arithmetic circuits.