{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T02:39:31Z","timestamp":1777516771353,"version":"3.51.4"},"reference-count":12,"publisher":"SAGE Publications","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["COM"],"published-print":{"date-parts":[[2018,12,19]]},"DOI":"10.3233\/com-180096","type":"journal-article","created":{"date-parts":[[2018,7,3]],"date-time":"2018-07-03T14:52:56Z","timestamp":1530629576000},"page":"67-98","source":"Crossref","is-referenced-by-count":0,"title":["Feasible set functions have small circuits"],"prefix":"10.1177","volume":"8","author":[{"given":"Arnold","family":"Beckmann","sequence":"first","affiliation":[{"name":"Department of Computer Science, Swansea University, UK. a.beckmann@swansea.ac.uk"}]},{"given":"Sam","family":"Buss","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of California, San Diego, USA. sbuss@ucsd.edu"}]},{"given":"Sy-David","family":"Friedman","sequence":"additional","affiliation":[{"name":"Kurt G\u00f6del Research Center, University of Vienna, Austria. sdf@logic.univie.ac.at"}]},{"given":"Moritz","family":"M\u00fcller","sequence":"additional","affiliation":[{"name":"Kurt G\u00f6del Research Center, University of Vienna, Austria. moritz.mueller@univie.ac.at"}]},{"given":"Neil","family":"Thapen","sequence":"additional","affiliation":[{"name":"Institute of Mathematics, Czech Academy of Sciences, Czech Republic. thapen@math.cas.cz"}]}],"member":"179","reference":[{"key":"10.3233\/COM-180096_ref1","unstructured":"P.\u00a0Aczel, Non-Well-Founded Sets, CSLI Lecture Notes, Vol.\u00a014, Center for the Study of Language and Information, Stanford, 1988."},{"key":"10.3233\/COM-180096_ref2","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1007\/s00153-015-0422-2","article-title":"Predicatively computable functions on sets","volume":"54","author":"Arai","year":"2015","journal-title":"Archive for Mathematical Logic"},{"key":"10.3233\/COM-180096_ref3","doi-asserted-by":"publisher","first-page":"730","DOI":"10.1017\/jsl.2015.26","article-title":"Safe recursive set functions","volume":"80","author":"Beckmann","year":"2015","journal-title":"Journal of Symbolic Logic"},{"key":"10.3233\/COM-180096_ref4","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.apal.2015.12.005","article-title":"Cobham recursive set functions","volume":"167","author":"Beckmann","year":"2016","journal-title":"Annals of Pure and Applied Logic"},{"key":"10.3233\/COM-180096_ref5","doi-asserted-by":"publisher","DOI":"10.1142\/9789813223523_0005"},{"key":"10.3233\/COM-180096_ref6","unstructured":"A.\u00a0Cobham, The intrinsic computational difficulty of functions, in: Logic, Methodology and Philosophy of Science, Proceedings of the Second International Congress, Held in Jerusalem, 1964, Y.\u00a0Bar-Hillel, ed., North-Holland, Amsterdam, 1965, pp.\u00a024\u201330."},{"key":"10.3233\/COM-180096_ref7","doi-asserted-by":"publisher","first-page":"567","DOI":"10.2307\/2586556","article-title":"Infinite time Turing machines","volume":"65","author":"Hamkins","year":"2000","journal-title":"Journal of Symbolic Logic"},{"key":"10.3233\/COM-180096_ref8","doi-asserted-by":"crossref","unstructured":"J.\u00a0H\u00e5stad, Almost optimal lower bounds for small depth circuits, in: Proceedings of the 18-th Annual ACM Symposium on Theory of Computing, 1986, pp.\u00a06\u201320.","DOI":"10.1145\/12130.12132"},{"key":"10.3233\/COM-180096_ref9","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0003-4843(72)90001-0","article-title":"The fine structure of the constructible hierarchy","volume":"4","author":"Jensen","year":"1972","journal-title":"Annals of Mathematical Logic"},{"key":"10.3233\/COM-180096_ref10","doi-asserted-by":"crossref","unstructured":"G.E.\u00a0Sacks, Higher Recursion Theory, Springer-Verlag, Berlin, 1990.","DOI":"10.1007\/978-3-662-12013-2"},{"key":"10.3233\/COM-180096_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-017-0487-8_5"},{"key":"10.3233\/COM-180096_ref12","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/s00605-002-0545-5","article-title":"P \u2260 N P for infinite time Turing machines","volume":"139","author":"Schindler","year":"2003","journal-title":"Monatshefte f\u00fcr Mathematik"}],"container-title":["Computability"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/COM-180096","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T15:59:59Z","timestamp":1777391999000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/COM-180096"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,19]]},"references-count":12,"journal-issue":{"issue":"1"},"URL":"https:\/\/doi.org\/10.3233\/com-180096","relation":{},"ISSN":["2211-3576","2211-3568"],"issn-type":[{"value":"2211-3576","type":"electronic"},{"value":"2211-3568","type":"print"}],"subject":[],"published":{"date-parts":[[2018,12,19]]}}}