Number of the records: 1
Feasible set functions have small circuits
- 1.
SYSNO ASEP 0499289 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve WOS Title Feasible set functions have small circuits Author(s) Beckmann, A. (GB)
Buss, S. (US)
Friedman, S.-D. (AT)
Müller, M. (AT)
Thapen, Neil (MU-W) RID, SAISource Title Computability. - : IOS Press - ISSN 2211-3568
Roč. 8, č. 1 (2019), s. 67-98Number of pages 32 s. Language eng - English Country NL - Netherlands Keywords computational complexity ; primitive recursive set functions ; circuit complexity ; Cobham recursive set functions Subject RIV IN - Informatics, Computer Science OECD category Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8) Method of publishing Limited access Institutional support MU-W - RVO:67985840 UT WOS 000472084400004 EID SCOPUS 85058974478 DOI 10.3233/COM-180096 Annotation 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. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2020 Electronic address http://dx.doi.org/10.3233/COM-180096
Number of the records: 1