Number of the records: 1  

Feasible set functions have small circuits

  1. 1.
    0499289 - MÚ 2020 RIV NL eng J - Journal Article
    Beckmann, A. - Buss, S. - Friedman, S.-D. - Müller, M. - Thapen, Neil
    Feasible set functions have small circuits.
    Computability. Roč. 8, č. 1 (2019), s. 67-98. ISSN 2211-3568
    EU Projects: European Commission(XE) 339691 - FEALORA
    Institutional support: RVO:67985840
    Keywords : computational complexity * primitive recursive set functions * circuit complexity * Cobham recursive set functions
    OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
    Method of publishing: Limited access
    http://dx.doi.org/10.3233/COM-180096

    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.
    Permanent Link: http://hdl.handle.net/11104/0291518

     
    FileDownloadSizeCommentaryVersionAccess
    Thapen1.pdf1310.7 KBPublisher’s postprintrequire
     
Number of the records: 1  

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