Sy Friedman (University of Vienna)
Computational Complexity and Set Theory

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 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 [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, Safe-recursive 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. 1381-1402, December 2011.