Journal article 954 views 171 downloads
Feasible set functions have small circuits
Arnold Beckmann 
,
Sam Buss,
Sy-David Friedman,
Moritz Müller,
Neil Thapen
,
Sam Buss,
Sy-David Friedman,
Moritz Müller,
Neil Thapen
Computability, Volume: 8, Issue: 1, Pages: 67 - 98
Swansea University Author:
Arnold Beckmann
-
PDF | Accepted Manuscript
Download (516.38KB)
DOI (Published version): 10.3233/COM-180096
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...
| Published in: | Computability |
|---|---|
| ISSN: | 22113568 22113576 |
| Published: |
2018
|
| Online Access: |
Check full text
|
| URI: | https://cronfa.swan.ac.uk/Record/cronfa40896 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| 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 |
| Issue: |
1 |
| Start Page: |
67 |
| End Page: |
98 |