FOM: Soare and complexity theory ...

John Case case at
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