Sy Friedman (University of Vienna)
I'll discuss two recent interactions between computational complexity
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  we use a set-theoretic analogue of the Bellantoni-Cook schemes of safe-recursion 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  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.
 A. Beckmann, S. Buss and S. Friedman, Safe-recursive set functions, in "The Infinity Project", Centre de Recerca Matematica Document Series, 2012.
 S. Buss, Y. Chen, J. Flum, S. Friedman and M. Mueller, Strong isomorphism reductions in complexity theory, Journal of Symbolic Logic, pp. 1381-1402, December 2011.