Bounded Arithmetic, Cryptography and Complexity
Samuel R. Buss · Theoria · 1997
This survey discusses theories of bounded arithmetic, growth rates of definable functions, natural proofs, interpolation theorems, connections to cryptography, and the di#culty of obtaining independence results.