Počet záznamů: 1  

Feasible set functions have small circuits

  1. 1. 0499289 - MU-W 2020 RIV NL eng J - Článek v odborném periodiku
    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
    GRANT EU: European Commission(XE) 339691 - FEALORA
    Institucionální podpora: RVO:67985840
    Klíčová slova: computational complexity * primitive recursive set functions * circuit complexity * Cobham recursive set functions
    Kód oboru RIV: IN - Informatika
    Obor OECD: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

    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.
    Trvalý link: http://hdl.handle.net/11104/0291518
    Název souboruStaženoVelikostKomentářVerzePřístup
    Thapen1.pdf1310.7 KBVydavatelský postprintvyžádat