Some consequences of our failure to prove non-linear lower bounds on explicit functions
R.J. Lipton · 2002
Investigates the consequences of assuming that no explicit function has non-polynomial size Boolean circuit complexity. There are many consequences of this assumption. For example, it immediately proves that P does not equal NP. It also has ramifications for the length of certain interactive proofs.>