Symmetric Functions Capture General Functions (Extended Abstract)

摘要

We show that the set of all functions is equivalent to the set of all symmetric functions (possibly over a larger domain) up to deterministic time complexity. In particular, for any function f, there is an equivalent symmetric function f_(sym) such that f can be computed from f_(sym) and vice-versa (modulo an extra deterministic linear time computation). For f over finite fields, f_(sym) is (necessarily) over an extension field. This reduction is optimal in size of the extension field. For polynomial functions, the degree of f_(sym) is not optimal. We present another reduction that has optimal degree "blowup" but is worse in the other parameters.