Počet záznamů: 1
Feasible set functions have small circuits
- 1.
SYSNO ASEP 0499289 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název Feasible set functions have small circuits Tvůrce(i) Beckmann, A. (GB)
Buss, S. (US)
Friedman, S.-D. (AT)
Müller, M. (AT)
Thapen, Neil (MU-W) RID, SAIZdroj.dok. Computability. - : IOS Press - ISSN 2211-3568
Roč. 8, č. 1 (2019), s. 67-98Poč.str. 32 s. Jazyk dok. eng - angličtina Země vyd. NL - Nizozemsko Klíč. slova computational complexity ; primitive recursive set functions ; circuit complexity ; Cobham recursive set functions Vědní obor RIV IN - Informatika Obor OECD Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8) Způsob publikování Omezený přístup Institucionální podpora MU-W - RVO:67985840 UT WOS 000472084400004 EID SCOPUS 85058974478 DOI 10.3233/COM-180096 Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2020 Elektronická adresa http://dx.doi.org/10.3233/COM-180096
Počet záznamů: 1