{"entities":{"Q2085583":{"pageid":2096325,"ns":120,"title":"Item:Q2085583","lastrevid":54423485,"modified":"2026-01-26T19:19:47Z","type":"item","id":"Q2085583","labels":{"en":{"language":"en","value":"Implicit recursion-theoretic characterizations of counting classes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7603660"}},"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":"Q2085583$083BA524-1108-4D11-BAC1-1FAFDE36744A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4625603b82fe3c71f477f293afb867ca2def5d2c","datavalue":{"value":{"text":"Implicit recursion-theoretic characterizations of counting classes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2085583$FD34F483-617E-48E9-93B1-551E4027A7C7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"42e69dae4d657b0baacaef5710bc0b1611a1e8d1","datavalue":{"value":"1506.03096","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2085583$ECD08EC0-1508-4FB5-A998-E718D11E1E4B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8f9aee8fa2e490413f426890c8aa34847b6dc293","datavalue":{"value":{"entity-type":"item","numeric-id":276253,"id":"Q276253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2085583$EBCF7C7C-06D6-486F-865A-0EC16E60CC4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d52212f331fdc13a9cc11beb0d62d5cf4d5a0cac","datavalue":{"value":{"entity-type":"item","numeric-id":194998,"id":"Q194998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2085583$6BC13174-7A2A-4008-8BAB-89806E5C955C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"74d5c1de56f651c607d14039fd75a8fd555b6c96","datavalue":{"value":{"entity-type":"item","numeric-id":276256,"id":"Q276256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2085583$0310D98B-8B5C-4F82-85FA-A86B11581E0A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a0a7cd28a9f85b9c6ad57bd5bb1ae477bfe37846","datavalue":{"value":{"entity-type":"item","numeric-id":114337,"id":"Q114337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2085583$4D3652BE-61CD-4E31-B8E1-18ADBD6D72D7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"56990fd6540c9785f009870b6cba51a68900b81f","datavalue":{"value":{"time":"+2022-10-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2085583$5C8BE7A2-A060-406A-84D8-86B1ECC06AB1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"118189bb81ef6d4b634c20f95769f206a19eb9f7","datavalue":{"value":"\\textit{L. G. Valiant} [Theor. Comput. Sci. 8, 189--201 (1979; Zbl 0415.68008)] introduced the class \\(\\#P\\) of all functions which count the number of accepting computations of non-deterministic Turing machines working in polynomial time. Later \\textit{K. W. Wagner} [Theor. Comput. Sci. 47, 131--147 (1986; Zbl 0637.03034)] introduced a hierarchy of counting functions FCH by allowing queries to functions of the previous level as follows: the level \\(0\\) coincides with the class of functions FPTIME introduced by \\textit{S. Bellantoni} and \\textit{S. Cook} [Comput. Complexity 2, No. 2, 97--110 (1992; Zbl 0766.68037)], and for \\(k>0\\), \\(\\# P_k=(\\#P)^{\\#P_{k-1}}\\), FCH =\\(\\bigcup_{k\\ge 0}\\{\\# P_k\\}\\). In particular, \\(\\# P_1=\\#P\\). Here for classes of functions \\(\\mathcal{F}\\) and \\(\\mathcal{G}\\), \\(\\mathcal{F}^{\\mathcal{G}}\\) denotes the class of all functions which can be computed with \\(\\mathcal{F}\\) resources but allowing oracle access to functions from \\(\\mathcal{G}\\). \\par In the paper under review, the authors give recursion-theoretic characterizations of all the levels \\(\\{\\# P_k\\}_{k\\in \\mathbb{N}}\\), and of FCH itself.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2085583$0910FA86-1924-4DBD-9337-803CEB48F126","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2085583$13628203-3E24-43C6-A0B7-DB3B5F6778FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2085583$A1224ACB-1EDC-4024-AF76-A2B810C17BDB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d1cc8425aa683c1e00079764728d32f5c5101007","datavalue":{"value":"7603660","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2085583$ACE1C380-1FAD-488B-AC95-8742B8736BC7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ca5077dd048c088806de416d08f29970c861169e","datavalue":{"value":"counting hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q2085583$DA6E4A68-F874-4160-A8FE-C95AE82B39F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9658e926be2a9e8bb6e8f2bc45fc26eb0d6cd6b5","datavalue":{"value":"implicit computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2085583$EF0456A3-C833-4A62-A158-936B28B83978","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"011c26a688b4884867881a22fe4f1204433e38c2","datavalue":{"value":"function algebras","type":"string"},"datatype":"string"},"type":"statement","id":"Q2085583$4F66A09D-5888-4B2C-A71D-1C53024389D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7501c5bafbe53a0833e9e6a641bb0d6b26e00d27","datavalue":{"value":"recursion-theoretic characterizations","type":"string"},"datatype":"string"},"type":"statement","id":"Q2085583$4290A93C-F283-4F49-B419-31E352E9FF62","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7c0f9a5de2afd25d103c132e1617d4201a3c58e4","datavalue":{"value":{"entity-type":"item","numeric-id":591972,"id":"Q591972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2085583$25533F4A-B2A2-4BBE-8CAD-6FBF6CE9B230","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":"Q2085583$316244F1-48C8-4F75-ACD2-606A56C962A1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6d8ba53fc45843a3c269a70f2d4c7056dc55cd4f","datavalue":{"value":"https://doi.org/10.1007/s00153-022-00828-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q2085583$6E13552B-5955-4505-9D9A-0005346D9B93","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"66399bec6b4882dfc7cc23530d9cbe8b880e0605","datavalue":{"value":"W4225321823","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2085583$898D7119-B8D2-4895-9B76-CD8114A34BE4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0942416bbb24094ad844c088479199c420a678b1","datavalue":{"value":{"entity-type":"item","numeric-id":1207333,"id":"Q1207333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2085583$154915D9-82C7-49F5-BEE9-8B72B681117C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c6e8cfa9e6eb9571f91dfe72363686a66d1eb6e","datavalue":{"value":{"entity-type":"item","numeric-id":1827390,"id":"Q1827390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2085583$047871BE-EBA1-481E-8350-38481A57CCED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ced343f864a0680ea50db15d085b4447139fedc1","datavalue":{"value":{"entity-type":"item","numeric-id":2882555,"id":"Q2882555"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2085583$C06E3229-7EE7-4A09-92BF-4B2CABE6ED1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae978bd620b682123250e58a731aadd5413dc2a4","datavalue":{"value":{"entity-type":"item","numeric-id":1407533,"id":"Q1407533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2085583$6D847956-5356-4FDC-93AF-160F31DC85DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0909c5baebe8e5f5a9e964f05c720f232deade69","datavalue":{"value":{"entity-type":"item","numeric-id":5586401,"id":"Q5586401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2085583$F17F4E8C-5F66-4EB3-AB43-A4D6B204FE1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9051039a48f7aed60da24d673938b0363ca24c24","datavalue":{"value":{"entity-type":"item","numeric-id":6168449,"id":"Q6168449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2085583$10E79F22-F9FA-47C0-A76C-76677CAF6812","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09ec65e395f02d63a980a349374a1113006b8bf6","datavalue":{"value":{"entity-type":"item","numeric-id":3487327,"id":"Q3487327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2085583$13F071D5-2ACA-4A47-8E4B-45FACD3B9058","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0fc880d8f3410c222225b6b2a9936a40416a74e6","datavalue":{"value":{"entity-type":"item","numeric-id":1894453,"id":"Q1894453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2085583$2DA06359-1ED8-4270-B4F8-33BB0764F6DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"433dbe3d64745b6b6c8b9c3f5350018c55dfdd49","datavalue":{"value":{"entity-type":"item","numeric-id":1946672,"id":"Q1946672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2085583$9EEC111D-7983-4F79-9A1F-1A3EA55BE61B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0633baa2c22ddc2ddf3c89da84d2dc9ec96eb60","datavalue":{"value":{"entity-type":"item","numeric-id":4850553,"id":"Q4850553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2085583$52D00F72-6E1D-4139-9360-EBFBBFD93BB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"157ef5e3428e1063f6b1385be5ffbf26b8711f0f","datavalue":{"value":{"entity-type":"item","numeric-id":4458695,"id":"Q4458695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2085583$879E26D4-9282-4BE3-89B4-56854BC472EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bdee229187821180cf0ed5f8f830754f9ccf330e","datavalue":{"value":{"entity-type":"item","numeric-id":3506329,"id":"Q3506329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2085583$C44B4599-DF2B-4307-8076-66E763DA5F90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bf500897a54d2e5101c3a2d054a645db1a124a6","datavalue":{"value":{"entity-type":"item","numeric-id":639668,"id":"Q639668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2085583$B353D57F-E6D1-4741-B98A-E89B76A0FE54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5384e80c5daf4018c733d902d1e9fc4a473b7060","datavalue":{"value":{"entity-type":"item","numeric-id":2062128,"id":"Q2062128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2085583$973F128C-A50F-4212-ACEA-6AA361B0769E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a46b20ae0ee21789871d8e63f85f91d2a1e7cf0","datavalue":{"value":{"entity-type":"item","numeric-id":1112020,"id":"Q1112020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2085583$12BAAA93-FC59-4CAF-9158-59BB22CB8C75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3199afbc552d4b782fb652485d98c16207457f9","datavalue":{"value":{"entity-type":"item","numeric-id":1427856,"id":"Q1427856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2085583$995AABDB-B450-4078-8276-B102834C006C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be78bc40947558fb5f5efe813f5826267126f11f","datavalue":{"value":{"entity-type":"item","numeric-id":3081651,"id":"Q3081651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2085583$4E779908-16AE-402B-8BAA-47FEB71BB66F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68c516460706e34bfacf776c096f40a576fd2116","datavalue":{"value":{"entity-type":"item","numeric-id":600247,"id":"Q600247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2085583$16EDC0C7-0309-4A69-8F67-F1FA812F369F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ae0a8ead3168e2d1e72f8983aea6304487c4d8f","datavalue":{"value":{"entity-type":"item","numeric-id":1365942,"id":"Q1365942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2085583$DEFE0401-A37C-458A-8DF9-0A9C13BC51F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2fe1787e2aa96eb740aa6a9f0eb2fadba2960d6","datavalue":{"value":{"entity-type":"item","numeric-id":1098837,"id":"Q1098837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2085583$B04C069F-33A3-4B60-92D9-02A78CAD5BE1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bebdfb10ad1eba2435e582e5f53d24d642fe1f3c","datavalue":{"value":"10.1007/S00153-022-00828-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2085583$F74F06D1-6240-4C74-8B76-82B692EEFD17","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"187edd84811e0420aaac0b5c008e1df70f66181a","datavalue":{"value":{"entity-type":"item","numeric-id":1365942,"id":"Q1365942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d286f77d23756980b532c1d0f864cfb64bab6417","datavalue":{"value":{"amount":"+0.8457622528076172","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":"Q2085583$32B5177E-8661-4DDD-9991-526779277B24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bcd0b0dcb80a617d29c308e7511d0349b0b3b951","datavalue":{"value":{"entity-type":"item","numeric-id":1098837,"id":"Q1098837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1310446843296483d829c9f6de97d7099beb8df6","datavalue":{"value":{"amount":"+0.8346621990203857","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":"Q2085583$1F73421B-D279-4A6E-AD95-9A4D1C74B7F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"259fea2324239cf8a5e3729df17de9ee4579190a","datavalue":{"value":{"entity-type":"item","numeric-id":3034822,"id":"Q3034822"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"97c70287f7685e1c28e8489a7aef88096cc8cbf3","datavalue":{"value":{"amount":"+0.7775389552116394","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":"Q2085583$F170CBF8-484C-4140-9B20-0428580C45DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3037abae775d1c0fe2794edbb26deab40322a9ab","datavalue":{"value":{"entity-type":"item","numeric-id":1894456,"id":"Q1894456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f9df713b58415ab9c9dec53ffba84a5c47e3b877","datavalue":{"value":{"amount":"+0.7519537210464478","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":"Q2085583$D487C9CA-E7E0-4CE9-A903-ABE54FEF2B92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d2f9b9e6284bd5bbb16ebcbf2f8a6c25b106f42a","datavalue":{"value":{"entity-type":"item","numeric-id":1008842,"id":"Q1008842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bbac4c8cfd6c2f31df90a0ebc2339bf0a56e1c56","datavalue":{"value":{"amount":"+0.7480390071868896","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":"Q2085583$BE067863-AE55-46B0-A5EA-BF6BEB562EF5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2085583","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2085583"}}}}}