Feasible set functions have small circuits

Article type: Research Article

Authors: Beckmann, Arnold^{a; *} | Buss, Sam^b | Friedman, Sy-David^c | Müller, Moritz^d | Thapen, Neil^e

Affiliations: [a] Department of Computer Science, Swansea University, UK. a.beckmann@swansea.ac.uk | [b] Department of Mathematics, University of California, San Diego, USA. sbuss@ucsd.edu | [c] Kurt Gödel Research Center, University of Vienna, Austria. sdf@logic.univie.ac.at | [d] Kurt Gödel Research Center, University of Vienna, Austria. moritz.mueller@univie.ac.at | [e] Institute of Mathematics, Czech Academy of Sciences, Czech Republic. thapen@math.cas.cz

Correspondence: [*] Corresponding author. a.beckmann@swansea.ac.uk.

Abstract: The Cobham Recursive Set Functions (CRSF) provide an analogue of polynomial time computation which applies to arbitrary sets. We give three new equivalent characterizations of CRSF. The first is algebraic, using subset-bounded recursion and a form of Mostowski collapse. The second is our main result: the CRSF functions are shown to be precisely the functions computed by a class of uniform, infinitary, Boolean circuits. The third is in terms of a simple extension of the rudimentary functions by transitive closure and subset-bounded recursion.

Keywords: Computational complexity, primitive recursive set functions, circuit complexity, Cobham recursive set functions

DOI: 10.3233/COM-180096

Journal: Computability, vol. 8, no. 1, pp. 67-98, 2019