FOM: Soare and complexity theory ...
John Case
case at mail.eecis.udel.edu
Tue Sep 15 12:30:55 EDT 1998
Bob Soare, in the 70s and 80s, influenced by the work of Manual Blum and his
students, produced (and/or directed) a number of papers applying RFT concepts
and methods to complexity theory.
For example:
Soare, R., ``Computational Complexity, Speedable and Levelable Sets,'' JSL
41 (1977), 545-563,
Bennison, V., and Soare, R., ``Some Lowness Properties and Computational
Complexity Sequences,'' Theoretical Computer Science 41 (1978), 233-254,
Soare, R., ``Computational Complexity of Recursively Enumerable Sets,''
Information and Control 52 (1982), 8-18.
Regarding Bob's circle, I note that he regularly visits Klaus Ambos-Spies in
Heidelberg and that the latter regularly applies RFT concepts and methods to
complexity theory.
(-8 John Case
More information about the FOM
mailing list