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. >
['Richard J. Lipton']
Some consequences of our failure to prove non-linear lower bounds on explicit functions