Feasible set functions have small circuits

DOI10.3233/COM-180096zbMath1459.03058WikidataQ129576527 ScholiaQ129576527MaRDI QIDQ5240585

Moritz Müller, Neil Thapen, Arnold Beckmann, Samuel R. Buss, Sy-David Friedman

Publication date: 28 October 2019

Published in: Computability (Search for Journal in Brave)

zbMATH Keywords

computational complexitycircuit complexityprimitive recursive set functionsCobham recursive set functions

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursive functions and relations, subrecursive hierarchies (03D20) Set theory (03E99) Higher-type and set recursion theory (03D65)

This page was built for publication: Feasible set functions have small circuits