Number of the records: 1  

Feasible set functions have small circuits

  1. 1.
    SYSNO ASEP0499289
    Document TypeJ - Journal Article
    R&D Document TypeJournal Article
    Subsidiary JČlánek ve WOS
    TitleFeasible 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, SAI
    Source TitleComputability. - : IOS Press - ISSN 2211-3568
    Roč. 8, č. 1 (2019), s. 67-98
    Number of pages32 s.
    Languageeng - English
    CountryNL - Netherlands
    Keywordscomputational complexity ; primitive recursive set functions ; circuit complexity ; Cobham recursive set functions
    Subject RIVIN - Informatics, Computer Science
    OECD categoryComputer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
    Method of publishingLimited access
    Institutional supportMU-W - RVO:67985840
    UT WOS000472084400004
    EID SCOPUS85058974478
    DOI10.3233/COM-180096
    AnnotationThe 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.
    WorkplaceMathematical Institute
    ContactJarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757
    Year of Publishing2020
    Electronic addresshttp://dx.doi.org/10.3233/COM-180096
Number of the records: 1  

  This site uses cookies to make them easier to browse. Learn more about how we use cookies.