Premium
Bounded Arithmetic, Cryptography and Complexity
Author(s) -
BUSS SAMUEL R.
Publication year - 1997
Publication title -
theoria
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.34
H-Index - 16
eISSN - 1755-2567
pISSN - 0040-5825
DOI - 10.1111/j.1755-2567.1997.tb00745.x
Subject(s) - arithmetic , cryptography , bounded function , citation , computer science , discrete mathematics , theoretical computer science , mathematics , information retrieval , world wide web , algorithm , mathematical analysis
This survey discusses theories of bounded arithmetic, growth rates of deflnable functions, natural proofs, interpolation theorems, connections to cryptography, and the di-culty of obtaining independence results.