{"entities":{"Q4934292":{"pageid":6963874,"ns":120,"title":"Item:Q4934292","lastrevid":108539408,"modified":"2026-11-06T21:58:03Z","type":"item","id":"Q4934292","labels":{},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1390027"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4934292$DCFC3B24-2C49-4CC2-9982-1E4F56D90F6C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"28a4ad1c8609ccf373b6082462fc77d94b853a68","datavalue":{"value":"0942.68049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4934292$F23BE77E-F2FF-4471-81DA-DF96D7FA20EC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"156c797a905a5f3fee298ee2b9f132ba806e98a8","datavalue":{"value":{"entity-type":"item","numeric-id":455764,"id":"Q455764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4934292$6FB4F276-EDD2-45B5-BD0A-567B23D26598","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a4dc3d990a0a8b8ad0b1a8a62e538a71a4d2cf07","datavalue":{"value":{"time":"+2000-07-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4934292$992D2A9E-1F8E-4106-9756-8D171470B71A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4934292$E562CAE8-30DD-4F4A-B05B-A9A4570BE708","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"33d9ad5fa3901c3c85d59a42af89ee043a9f83fb","datavalue":{"value":"03D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4934292$1857B53A-6836-45A2-A19C-2E28A29E604D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4934292$6872C140-B1A7-41D1-8266-FED7B18BE380","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"89663cdc2c9f64b2cd0a104bcac86329d89b9b2d","datavalue":{"value":"03-02","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4934292$D724EF98-F902-4D02-B522-1DACAD842E83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6ee9f5484d11a01fb95552e5bea2154ebac0877","datavalue":{"value":"03D20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4934292$1CA333C1-6B88-4A76-800B-F1B20C0161B8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cc4564eddc6dc7536c6dbe502503cd43cce94dfa","datavalue":{"value":"1390027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4934292$0B699A81-6D62-4BBA-BBF6-D934DED53D6D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7956c7f6df536e6143a1c2159e2cd8230dcb1d96","datavalue":{"value":"computable function","type":"string"},"datatype":"string"},"type":"statement","id":"Q4934292$D7EB343D-56D2-464B-8C58-0472060A8CF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ab1b88d2b2ce7293175b5ce95822467df0ca5012","datavalue":{"value":"function algebra","type":"string"},"datatype":"string"},"type":"statement","id":"Q4934292$96512F9E-9776-45A8-9076-FF05F0C54885","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"08587a98f8badb5f4d6c92d80c565bf1335480a9","datavalue":{"value":"computation model","type":"string"},"datatype":"string"},"type":"statement","id":"Q4934292$68037B97-7972-4864-8AFD-B9F23F020D13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0ff22fde538525b3a4079601bc5c637861c213d7","datavalue":{"value":"recursion scheme","type":"string"},"datatype":"string"},"type":"statement","id":"Q4934292$16B92110-E584-4464-A010-8496DE40624B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"667a668191729395ef18f011f2ed64a27be3fd2d","datavalue":{"value":"type 2 functional","type":"string"},"datatype":"string"},"type":"statement","id":"Q4934292$3C1E71D7-21BF-4E60-8060-A3D7B52D44F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"421a43f4b0e8832a026eaa34353c95869f115bee","datavalue":{"value":"survey","type":"string"},"datatype":"string"},"type":"statement","id":"Q4934292$91073F29-0FE9-48FC-8E8F-0ECDE6C8959D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bfa40d769f07cdfbcfc8196efb73c1253dbfc567","datavalue":{"value":"primitive recursive functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q4934292$D37C2B61-188A-4DB3-88E2-DFDFD22FD65F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1408da7db4c03e08918a50622f2fb337e63ab39f","datavalue":{"value":"complexity classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q4934292$C445E07C-A344-4073-B7CF-3EEFA71EB53A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"78bf85b708483ce32a618b472f5db46a47f44067","datavalue":{"value":"quantifier hierarchies","type":"string"},"datatype":"string"},"type":"statement","id":"Q4934292$4F5E5D9E-70F8-4AE8-95D6-9729223B6B39","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4934292$8C87BAEE-0B69-4BD8-99CB-FA0D65D7262A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"14acbe104ccb93c604df6717358b7102527441df","datavalue":{"value":{"entity-type":"item","numeric-id":1332666,"id":"Q1332666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"66872b926a0c34b8f7720f93747837cae6ef572c","datavalue":{"value":{"amount":"+0.7771663665771484","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4934292$BB008071-F9C6-4E58-BAD6-B6462D856E83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc67a5540e42c6fdeee2c542f87049833d065d0c","datavalue":{"value":{"entity-type":"item","numeric-id":1587346,"id":"Q1587346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"25c7defc4ada34dd36b4a27e68becb7bd0c61212","datavalue":{"value":{"amount":"+0.7768114805221558","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4934292$1704C1F3-5A7A-4884-9460-9347DBF1A537","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f564c3d94c2c5df9834cf7ba05405c27c8f1e663","datavalue":{"value":{"entity-type":"item","numeric-id":4341956,"id":"Q4341956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a3a5bf9736ec903b3b7ebe27bf3ede7c75cf646","datavalue":{"value":{"amount":"+0.7595958113670349","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4934292$E6DCA4AA-6849-4F51-A8C3-90A9FF092051","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8222332d37e53e08d1bbaaf823df0047b0693d6","datavalue":{"value":{"entity-type":"item","numeric-id":1781116,"id":"Q1781116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6cc0dddaf76816768ba282c42881b5995160a1cc","datavalue":{"value":{"amount":"+0.7557538151741028","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4934292$233601AA-B94C-425A-870A-C23355543EC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"796c2f7fa0ad617d1c120fccc93754bc1a8c09c2","datavalue":{"value":{"entity-type":"item","numeric-id":3690806,"id":"Q3690806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a1b85209240d42f7bfed5bed43f6ab935e0616e","datavalue":{"value":{"amount":"+0.754011332988739","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4934292$4C38C8CC-D813-4AC7-B6A6-324680D500FC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3949f47401d7293db3f4cd6522bb473e6634be44","datavalue":{"value":"A function algebra is a smallest class of functions containing some initial functions and being closed under some operations (e.g., composition of functions or primitive recursion). In 1975 Kurt G\u00f6del envisioned a classification of all total recursive functions as a hierarchy of function algebras, allowing operations of growing complexity. The present paper surveys some work that has been done in the past decades on algebraic characterizations of subclasses of the primitive recursive functions and their relation to computational complexity theory. Some of the presented results are: a characterization of the logtime hierarchy \\(\\text{LH}\\) (known to coincide with the constant-depth circuit class \\(\\text{ AC}^0\\)) by an algebra \\(A_0\\) defined from a family of basic functions by composition and so-called concatenation recursion on notation; a characterization of \\(\\text{ TC}^0\\) by allowing in the above multiplication as an additional initial function; a characterization of \\(\\text{ NC}\\) by adding to the above the operation of so-called weak bounded recursion on notation; characterizations of time- and space-bounded complexity classes by algebras using the operation of bounded recursion; characterizations of quantifier hierarchies such as the linear time hierarchy or the polynomial time hierarchy using bounded minimization. Further results concern safe recursion schemes and classes of type 2 functionals. An interesting open questions that is discussed concerns the class \\(\\mathcal K\\), defined by \\textit{R. L. Constable} ``Type two computational complexity'', Proc. 5th ann.~ACM Symp.~Theor.~Comput., Austin 1973, 108-121 (1973; Zbl 0306.68022)]. In that paper it is claimed without proof that \\(\\mathcal K\\) is the class of all polynomial-time computable functions. However, today it is suspected that this claim is wrong and the question remains to what complexity class Constable's class \\(\\mathcal K\\) corresponds. For the entire collection see [Zbl 0923.03001].","type":"string"},"datatype":"string"},"type":"statement","id":"Q4934292$9B8288B8-0311-4A6A-8E2E-924185880E6C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4934292","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4934292"}}}}}