Cobham recursive set functions
type: Item
instance of: scholarly article
title: Cobham recursive set functions
zbMATH Open document ID: 1383.03050
author: Arnold Beckmann
author: Sy-David Friedman
author: Moritz Müller
author: Neil Thapen
author: Samuel R. Buss
published in: Annals of Pure and Applied Logic
publication date: 2016-01-12T00:00:00Z
review text: Computational complexity keeps being inspired by one of the original definitions of polynomial time computable functions [\textit{A. Cobham}, in: Logic, methodology and philosphy of science. Proceedings of the 1964 international congress. Amsterdam: North-Holland Publishing Company. 24--30 (1965; Zbl 0192.08702)]: instead of defining complexity class in terms of alternation, space or time on an abstract machine, it is possible to define a ``method'' to construct functions that will provably always be computable in polynomial time on an abstract machine. This constitutes an interesting shift from a mere observation to a mathematical proof, and opens the door to a more mathematical way of comparing complexity classes. The original definition, using limited recursion on notation, applies to functions taking as input binary strings. This paper asks (and answers positively) a simple question: is it possible to do the same for sets, i.e., to pinpoint a set of principles that will generate all the functions on set computable on polynomial time, and only those? This question was already asked, and (partially) answered, with the creation of safe recursive set functions (SRSF) [\textit{A. Beckmann} et al., J. Symb. Log. 80, No. 3, 730--762 (2015; Zbl 1357.03075)] and predicatively computable set functions (PCSF) [\textit{T. Arai}, Arch. Math. Logic 54, No. 3--4, 471--485 (2015; Zbl 1371.03094)]. The answer provided in this paper, called ``Cobham recursive set functions'' (CRSF) compares to those approaches as follows: {\parindent=0.7cm \begin{itemize}\item[--] SRSF actually failed to characterize polynomial time functions, but characterized multiple other complexity classes (depending on the restrictions on the sets considered). \item[--] PCSF characterizes polynomial functions on binary strings when restricted to hereditarily finite sets: its exact computational power on non-hereditarily finite sets remains unknown. \item[--] CRSF, when restricted to encoding of finite binar…
reviewed by: Clément Aubert
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03D20
Mathematics Subject Classification ID: 03E99
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 6529284
zbMATH Keywords: set function
zbMATH Keywords: polynomial time
zbMATH Keywords: Cobham recursion
zbMATH Keywords: smash function
zbMATH Keywords: hereditarily finite
zbMATH Keywords: rudimentary function
MaRDI profile type: Publication
full work available at URL: j.apal.2015.12.005
OpenAlex ID: W2252118216
cites work: Predicatively computable functions on sets
cites work: SAFE RECURSIVE SET FUNCTIONS
cites work: A new recursion-theoretic characterization of the polytime functions
cites work: Q3794177
cites work: Q5586401
cites work: The fine structure of the constructible hierarchy
cites work: Q4726219
cites work: Q4395612
DOI: 10.1016/J.APAL.2015.12.005
Recommended article: Q4223288
Recommended article: COBHAM RECURSIVE SET FUNCTIONS AND WEAK SET THEORIES
Recommended article: Q3283893
Recommended article: Recursive functions
Recommended article: Farey recursive functions
Recommended article: Recursive functionals
Recommended article: SAFE RECURSIVE SET FUNCTIONS
Recommended article: Recursive set relations
Recommended article: Power set recursion
description: scientific article; zbMATH DE number 6529284