No Cover Image

Journal article 1089 views 194 downloads

Feasible set functions have small circuits

Arnold Beckmann Orcid Logo, Sam Buss, Sy-David Friedman, Moritz Müller, Neil Thapen

Computability, Volume: 8, Issue: 1, Pages: 67 - 98

Swansea University Author: Arnold Beckmann Orcid Logo

Check full text

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...

Full description

Published in: Computability
ISSN: 22113568 22113576
Published: 2018
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa40896
first_indexed 2018-06-30T19:28:28Z
last_indexed 2020-06-29T18:54:51Z
id cronfa40896
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2020-06-29T17:24:26.3784382</datestamp><bib-version>v2</bib-version><id>40896</id><entry>2018-06-30</entry><title>Feasible set functions have small circuits</title><swanseaauthors><author><sid>1439ebd690110a50a797b7ec78cca600</sid><ORCID>0000-0001-7958-5790</ORCID><firstname>Arnold</firstname><surname>Beckmann</surname><name>Arnold Beckmann</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2018-06-30</date><deptcode>MACS</deptcode><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.</abstract><type>Journal Article</type><journal>Computability</journal><volume>8</volume><journalNumber>1</journalNumber><paginationStart>67</paginationStart><paginationEnd>98</paginationEnd><publisher/><issnPrint>22113568</issnPrint><issnElectronic>22113576</issnElectronic><keywords>computational complexity, primitive recursive set functions, circuit complexity, Cobham recursive set functions</keywords><publishedDay>19</publishedDay><publishedMonth>12</publishedMonth><publishedYear>2018</publishedYear><publishedDate>2018-12-19</publishedDate><doi>10.3233/COM-180096</doi><url>https://www.iospress.nl/journal/computability/</url><notes/><college>COLLEGE NANME</college><department>Mathematics and Computer Science School</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>MACS</DepartmentCode><institution>Swansea University</institution><apcterm/><lastEdited>2020-06-29T17:24:26.3784382</lastEdited><Created>2018-06-30T17:46:46.9980888</Created><authors><author><firstname>Arnold</firstname><surname>Beckmann</surname><orcid>0000-0001-7958-5790</orcid><order>1</order></author><author><firstname>Sam</firstname><surname>Buss</surname><order>2</order></author><author><firstname>Sy-David</firstname><surname>Friedman</surname><order>3</order></author><author><firstname>Moritz</firstname><surname>M&#xFC;ller</surname><order>4</order></author><author><firstname>Neil</firstname><surname>Thapen</surname><order>5</order></author></authors><documents><document><filename>0040896-20092018104920.pdf</filename><originalFilename>40896.pdf</originalFilename><uploaded>2018-09-20T10:49:20.4230000</uploaded><type>Output</type><contentLength>476233</contentLength><contentType>application/pdf</contentType><version>Accepted Manuscript</version><cronfaStatus>true</cronfaStatus><embargoDate>2018-09-19T00:00:00.0000000</embargoDate><copyrightCorrect>true</copyrightCorrect><language>eng</language></document></documents><OutputDurs/></rfc1807>
spelling 2020-06-29T17:24:26.3784382 v2 40896 2018-06-30 Feasible set functions have small circuits 1439ebd690110a50a797b7ec78cca600 0000-0001-7958-5790 Arnold Beckmann Arnold Beckmann true false 2018-06-30 MACS 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. Journal Article Computability 8 1 67 98 22113568 22113576 computational complexity, primitive recursive set functions, circuit complexity, Cobham recursive set functions 19 12 2018 2018-12-19 10.3233/COM-180096 https://www.iospress.nl/journal/computability/ COLLEGE NANME Mathematics and Computer Science School COLLEGE CODE MACS Swansea University 2020-06-29T17:24:26.3784382 2018-06-30T17:46:46.9980888 Arnold Beckmann 0000-0001-7958-5790 1 Sam Buss 2 Sy-David Friedman 3 Moritz Müller 4 Neil Thapen 5 0040896-20092018104920.pdf 40896.pdf 2018-09-20T10:49:20.4230000 Output 476233 application/pdf Accepted Manuscript true 2018-09-19T00:00:00.0000000 true eng
title Feasible set functions have small circuits
spellingShingle Feasible set functions have small circuits
Arnold Beckmann
title_short Feasible set functions have small circuits
title_full Feasible set functions have small circuits
title_fullStr Feasible set functions have small circuits
title_full_unstemmed Feasible set functions have small circuits
title_sort Feasible set functions have small circuits
author_id_str_mv 1439ebd690110a50a797b7ec78cca600
author_id_fullname_str_mv 1439ebd690110a50a797b7ec78cca600_***_Arnold Beckmann
author Arnold Beckmann
author2 Arnold Beckmann
Sam Buss
Sy-David Friedman
Moritz Müller
Neil Thapen
format Journal article
container_title Computability
container_volume 8
container_issue 1
container_start_page 67
publishDate 2018
institution Swansea University
issn 22113568
22113576
doi_str_mv 10.3233/COM-180096
url https://www.iospress.nl/journal/computability/
document_store_str 1
active_str 0
description 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.
published_date 2018-12-19T07:28:44Z
_version_ 1821389645014892544
score 11.04748

Similar Items