I will define a class CRSF of "polynomial time functions" on arbitrary sets. The definition is in the spirit of Cobham's definition of polynomial time function on strings, in that we can only define a function by recursion if we already know a bound on the complexity of its output. I will show that on binary strings this gives the usual polynomial time functions, and that, for a suitable definition of circuit complexity for sets, every function in CRSF has small circuits.
A general theme is that CRSF can be understood as a model of parallel computation over directed acyclic graphs, where the graph of the computation can only be polynomially more complex than the graph given as input.
Joint work with Arnold Beckmann, Sam Buss, Sy Friedman and Moritz Mueller.
EN
