{"entities":{"Q5465359":{"pageid":7494918,"ns":120,"title":"Item:Q5465359","lastrevid":109589306,"modified":"2026-11-13T04:42:59Z","type":"item","id":"Q5465359","labels":{},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2196512"}},"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":"Q5465359$F1E8AE9D-89B7-40BB-9339-B07217A307C4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5d8cf7ae9ec6e11de1e114da5f048f6c7d380b25","datavalue":{"value":"1084.03044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5465359$E0B15DBD-6D1C-4243-84DB-FDFABAA403DF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1dd83e30b5291de8829d091c1ba44aab3df736da","datavalue":{"value":{"time":"+2005-08-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5465359$F8A17900-456A-44DF-AFDD-56ACB52D1DDE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ece9b879f80d96e2a1d45b28bdcc8cfa6b01861e","datavalue":{"value":"03F20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5465359$5A92815C-219B-4407-8122-3CFC47BE4761","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5465359$E449CC57-2659-4A65-A800-2F8EBC909C68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5465359$19E277F9-F1DD-4A5E-90E2-F354F79C8186","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5465359$AB86757A-6E4F-4C0E-BCDC-D616C56560A2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"63e927d639b726ac8a6f576f65957fcf875de2f7","datavalue":{"value":"2196512","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5465359$E8051106-EAC6-46FD-A7D9-6440154B30EF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f8db1726c03c7059c08d69b8aca64a6baa1151a9","datavalue":{"value":"complexity class","type":"string"},"datatype":"string"},"type":"statement","id":"Q5465359$5D560173-E8F1-4CC4-8285-6FEA80EF342D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e35064add7a9203564a51afec68515c9bfc2fe36","datavalue":{"value":"quantified propositional system","type":"string"},"datatype":"string"},"type":"statement","id":"Q5465359$04EF1ABA-27A6-42B6-8C93-28821712FB03","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"00ef32c5864b607ccf80c983c44b8c3fc4484c5b","datavalue":{"value":{"entity-type":"item","numeric-id":1096389,"id":"Q1096389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5465359$568DB34A-D9AD-43FD-8A70-33F9CF0512A4","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":"Q5465359$C540A4DC-71CB-401E-AA29-E3D605DC4DA9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f9220e9c37dda4ea4e27fdfbfd6ec9ec1aa7ec1","datavalue":{"value":{"entity-type":"item","numeric-id":5306365,"id":"Q5306365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f3e2a11a140073f6bd278e79dd428143dbdb9b0","datavalue":{"value":{"amount":"+0.8248820900917053","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":"Q5465359$44316442-1B16-461E-9061-58F66A9A8926","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2452193748cc5ba266bc3360acefd5886e7992b","datavalue":{"value":{"entity-type":"item","numeric-id":1192345,"id":"Q1192345"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e71d236978d156e3822ce80a998782db39c941a","datavalue":{"value":{"amount":"+0.8168977499008179","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":"Q5465359$FECA32E8-56C9-493F-9422-66BAAEBC0F47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"694c8995e5adde426b67d4160ef15ab11f60d065","datavalue":{"value":{"entity-type":"item","numeric-id":5310650,"id":"Q5310650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d67178c55c2570fa3c13d5bfaac5df7b7ac08fed","datavalue":{"value":{"amount":"+0.7778701186180115","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":"Q5465359$E9F7EA04-C7F1-4ADC-9F8B-D9B6AACEB1EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5aad5a2da2592ee962691785dae83be1d3fe8744","datavalue":{"value":{"entity-type":"item","numeric-id":3087409,"id":"Q3087409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"822d92861e6b9d64d88a124035b91fa6720fb51c","datavalue":{"value":{"amount":"+0.7604430317878723","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":"Q5465359$088159BC-45C6-4045-87CB-49E284B39CDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8704eddf7938792d74605c5101951228bbf06158","datavalue":{"value":{"entity-type":"item","numeric-id":4850548,"id":"Q4850548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d6e6dfee6db9b62ec1c59f9f68ab0bf44d9237f3","datavalue":{"value":{"amount":"+0.7543848156929016","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":"Q5465359$A80E61A9-A0A2-4E91-AB71-47E21552AA3F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dfafb2c8c0dcf927ab6b7bc9ae2e817a8147203d","datavalue":{"value":"This article begins thus: ``An important part of bounded arithmetic is associating logical theories with various complexity classes, and then translating proofs in those theories to families of proofs in appropriate propositional (or quantified propositional) proof systems. Our purpose here is to give a unified treatment of this three-way association to the sequence of complexity classes \\[ \\text{AC}^0\\subset \\text{AC}^0(2)\\subset \\text{TC}^0\\subseteq \\text{NC}^1\\subseteq \\text{L}\\subseteq \\text{NL}\\subseteq \\text{NC}\\subseteq \\text{P}, \\] where P is the class of problems solvable in polynomial time.'' As the author says, ``in the literature there is a hodge-podge of theories associated with these complexity classes'' -- equational, 1-sorted, 2-sorted, etc. Hence, a good unified treatment as in this article is certainly a great service. The author uses 2-sorted languages (one sort for numbers, and the other for finite sequences of 0 and 1). He starts from basic definitions, explains each complexity class, and sets up the matching theory. Of course, the correctness of the match is proved or referred to the literature. Translations into quantified propositional systems are carefully given, but not many results or theorems are mentioned. There are abundant comments on past achievements and future work, including the comparison of the author's 2-sorted approach with Kraj\u00ed\u010dek's 1-sorted one. For the entire collection see [Zbl 1062.68004].","type":"string"},"datatype":"string"},"type":"statement","id":"Q5465359$D8663F37-DA7F-4D01-A91C-E63F003EBA65","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5465359","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5465359"}}}}}