Feasible set functions have small circuits

0499289 - MÚ 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
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
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.
Trvalý link: http://hdl.handle.net/11104/0291518