Sy Friedman (University of Vienna)

I'll discuss two recent interactions between computational complexity
theory
and set theory.
What does it mean for a function on sets to be computable in polynomial time? In joint work with Beckmann and Buss [1] we use a settheoretic analogue of the BellantoniCook schemes of saferecursion to answer this question. Can set theory offer new approaches to problems in computational complexity theory? In joint work with Buss, Chen, Flum and Mueller [2] we provide a positive answer to this question by studying the natural analogue of Borel reducibility for isomorphism relations on PTIME classes of finite structures. [1] A. Beckmann, S. Buss and S. Friedman, Saferecursive set functions, in "The Infinity Project", Centre de Recerca Matematica Document Series, 2012. [2] S. Buss, Y. Chen, J. Flum, S. Friedman and M. Mueller, Strong isomorphism reductions in complexity theory, Journal of Symbolic Logic, pp. 13811402, December 2011. 