Feasible set functions have small circuits

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F19%3A00499289" target="_blank" >RIV/67985840:_____/19:00499289 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.3233/COM-180096" target="_blank" >http://dx.doi.org/10.3233/COM-180096</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.3233/COM-180096" target="_blank" >10.3233/COM-180096</a>

Result language

angličtina

Original language name

Feasible set functions have small circuits

Original language description

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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2019

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Computability

ISSN

2211-3568

e-ISSN

—

Volume of the periodical

8

Issue of the periodical within the volume

1

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

32

Pages from-to

67-98

UT code for WoS article

000472084400004

EID of the result in the Scopus database

2-s2.0-85058974478