{"entities":{"Q868664":{"pageid":870512,"ns":120,"title":"Item:Q868664","lastrevid":50044867,"modified":"2026-01-12T19:08:49Z","type":"item","id":"Q868664","labels":{"en":{"language":"en","value":"Computational complexity of logical theories of one successor and another unary function"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5131234"}},"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":"Q868664$05BA2F50-C9C6-4627-8820-01408EE87D5D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2cefdbae05a9088d9d52dd9341c427a173e1b66c","datavalue":{"value":{"text":"Computational complexity of logical theories of one successor and another unary function","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q868664$BD8BB288-3EBE-45D9-918E-C35308D2A25A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"69d9f109a1d3975c5341a489ec4b854cfa90acbd","datavalue":{"value":"1110.03025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868664$16C0C974-7A46-4B88-BB7F-2AB2C8E9121C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cf8dc75668fbe01557231ec0e2459242b9425887","datavalue":{"value":{"entity-type":"item","numeric-id":688515,"id":"Q688515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868664$32C2E89A-9E99-4AB3-829B-CABC884E3B2F","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":"Q868664$51033A15-DA32-4AEF-BFE3-CE8AE8DECD79","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f5823d03fbcff5d473b8034cff96a416b6d05e19","datavalue":{"value":{"time":"+2007-03-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q868664$631474B0-AEA4-4E18-89A9-C37670210A4A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"75e2d9a3394f8a957a23f9f11da0b282bafd99b6","datavalue":{"value":"This paper studies the set of natural numbers as a universe equipped with equality as the unique relation and simple, usual unary, functions as basic operations. The logic theory derived from the above is proven to be complete for some choices of the unary function. In particular, it is known that this is the case for the unary functions \\(x+1\\), \\(2x\\), \\(x^2\\) and \\(2^x\\), where equality is the only relation assumed. The author extends the result to the first-order logical theory derived by the function \\(x+1\\) combined with the functions \\(c^x\\) and \\(x^c\\).  The article begins with an overview of the necessary definitions and other preliminaries, which is then followed with an extensive series of theorems, lemmas and corollaries with complete proofs. Completeness is assumed for the class ATIME-ALT\\((2^{O(n)},O(n))\\) throughout this article. The paper concludes with a list of relevant articles.","type":"string"},"datatype":"string"},"type":"statement","id":"Q868664$F561B7AF-3A82-4AB2-8061-A65037C82FDB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"58309c80337e7309a39fa8b39c69e1b722b3cd2b","datavalue":{"value":{"entity-type":"item","numeric-id":590170,"id":"Q590170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868664$56A7DD21-64C3-45F9-8C04-CBBA12B3CCFD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868664$6B3CBBD0-1A8D-4C56-9C73-20C890CDBC31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"407654cf92f0702e03297e7fe541e25fa3f13c2d","datavalue":{"value":"03B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868664$4CEA477E-7CAF-4175-B82D-57E94D744DB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868664$A9639E64-F808-434D-B6A9-9CC84C4DE3DC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"eb9f11ad6fdba792db7b093016ae53a51823e69e","datavalue":{"value":"5131234","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868664$7C5E8914-AD19-435F-9A76-44D165212AF3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q868664$01F33DBE-2A3F-4B7C-93E1-D451FCE14706","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2400f038a313a4b0f1ef5407932d4864ff4e95fa","datavalue":{"value":"logical theories","type":"string"},"datatype":"string"},"type":"statement","id":"Q868664$7700521E-354D-4782-805C-79DA18CC9ADD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f9e45e72898ab5ef3149ddc99da95e7adb07eff4","datavalue":{"value":"Ehrenfeucht-Fra\u00efss\u00e9 games","type":"string"},"datatype":"string"},"type":"statement","id":"Q868664$F63B5F3B-9468-4EA0-824F-A2A8DA9DBF6A","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":"Q868664$9BCCB93E-829B-49AE-84C2-6EF06E5C757F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"44f2ebce478bf218bd8cf6112c44f7d4209ed3e5","datavalue":{"value":"https://doi.org/10.1007/s00153-006-0031-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q868664$895792D6-1D19-45F9-9357-C258E8B873EA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3f915982b6cf0c72a8472b9a27c069f837a78567","datavalue":{"value":"W2160473480","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868664$1754E59E-98AB-4862-BC48-0E601D2AA452","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9cfc53db72d247da5f30e677d4e958d296619aa4","datavalue":{"value":{"entity-type":"item","numeric-id":3996675,"id":"Q3996675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868664$49694DB6-A4E5-47DC-B8F3-81BD0AD64334","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d74eec834971a75b92aae841b2c83f9c1a887997","datavalue":{"value":{"entity-type":"item","numeric-id":1159661,"id":"Q1159661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868664$AFAB99EE-70BB-4B0C-87FE-2F1F7C832E5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a419dd7ff0f3d465e478a0d405d767ee1f50956e","datavalue":{"value":{"entity-type":"item","numeric-id":917543,"id":"Q917543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868664$F243421D-1A02-4122-AF56-7F2874E15704","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"668a8637c081f79751e1e57f52557e1f7bc7f98a","datavalue":{"value":{"entity-type":"item","numeric-id":3274971,"id":"Q3274971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868664$2B2F6483-DEC0-4C5E-B7F6-B832290F0A6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f84c82de96fb7c7b710e84da042fa6d2d7d4ea68","datavalue":{"value":{"entity-type":"item","numeric-id":5520636,"id":"Q5520636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868664$FA9C049C-6D44-4E09-90BD-4A426D21D72B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29035f06020bdf6a821f5c6e4a2fac381017baf3","datavalue":{"value":{"entity-type":"item","numeric-id":1256445,"id":"Q1256445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868664$70346A7D-22DF-4253-BCA4-D079AFA5BE51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c3f72e4cfa0d440af72fe380c939fa418d344db","datavalue":{"value":{"entity-type":"item","numeric-id":3666827,"id":"Q3666827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868664$3F6C224F-E416-44EC-9041-C039AF01B8EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b96d86ffe51ba0a248199198af52b51f96a869c3","datavalue":{"value":{"entity-type":"item","numeric-id":1333250,"id":"Q1333250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868664$7EA4E457-E297-48DD-B54F-6E50768A9134","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e6ee93c6a75b541cd72652bc62d7edbd6011d59","datavalue":{"value":{"entity-type":"item","numeric-id":5941257,"id":"Q5941257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868664$B0AA372E-9040-47F8-B605-6AA9F25698AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"426a0bd9295cad4f8cf98e97bc1dcda5a791b9e1","datavalue":{"value":{"entity-type":"item","numeric-id":1100188,"id":"Q1100188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868664$644D7529-465E-4B83-8FC1-6FAA2A9E1E52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c2eb3cbdc42a7d4b6c4f13bfbc177f58cb09580","datavalue":{"value":{"entity-type":"item","numeric-id":1202924,"id":"Q1202924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868664$64CA8B9E-2083-4A2E-8FFC-0D837FC04C1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37d179bdd83dd52ebb1134a0d415ec33f0098896","datavalue":{"value":{"entity-type":"item","numeric-id":3328515,"id":"Q3328515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868664$9FAF6009-1032-49D7-B614-89B7F27143BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03fa29f408ff026c6819da9ba06a75ba37e65447","datavalue":{"value":{"entity-type":"item","numeric-id":752739,"id":"Q752739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868664$9D165BA1-6ADB-4DFB-A272-032A30E3FCD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f5d16eaebef48efb59558189ec48771d81154c86","datavalue":{"value":{"entity-type":"item","numeric-id":4088806,"id":"Q4088806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868664$8471A278-0A27-45FF-BEE4-71A2F4D79138","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3edfa56e27db92ffca6f4798f086ec18992b6864","datavalue":{"value":{"entity-type":"item","numeric-id":793017,"id":"Q793017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868664$D853E2C4-C73D-4BAE-880E-1726EA310F28","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b2104699af561f56a9aa0afa3e33f8e15cc38945","datavalue":{"value":"10.1007/S00153-006-0031-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868664$5EAA4BBD-752A-4B1D-B116-B64DBB0BE6EC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"75fd85a6ffc0d67d138d1414d90131f2b421d99a","datavalue":{"value":{"entity-type":"item","numeric-id":1202924,"id":"Q1202924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d6e3b63e73bb05530f14dfe7cc2e3fdb3e9d925a","datavalue":{"value":{"amount":"+0.6778072714805603","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":"Q868664$31D83CC2-0357-49B8-B82D-87F50EE61428","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c29bea006d350c0559b7f4691efd2114866fe8bc","datavalue":{"value":{"entity-type":"item","numeric-id":4386803,"id":"Q4386803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76a0ad34d7e3e9877761e1dd55b01e73ad875020","datavalue":{"value":{"amount":"+0.6770188212394714","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":"Q868664$F5AD7AA3-68A3-4EEF-8408-B9E33F242EF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f7e14441c74267c6625f32c3cd4053fae579e4a","datavalue":{"value":{"entity-type":"item","numeric-id":4865977,"id":"Q4865977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e8955f09fd514354b08398e77a1eefecb289451d","datavalue":{"value":{"amount":"+0.6764822006225586","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":"Q868664$763F30AB-D156-41FF-B2D6-14021500F1CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1938d98e87c34cc9554a6a1ce2d2c44d94cc4cbd","datavalue":{"value":{"entity-type":"item","numeric-id":3362716,"id":"Q3362716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d3ef5d53777f9bfd7278f1073e17956847060af","datavalue":{"value":{"amount":"+0.6714189052581787","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":"Q868664$642D4104-CFD0-45C2-BB1F-1CFE4343E271","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c04c3cea3e46fa9091d90969e3027262d67b3c7","datavalue":{"value":{"entity-type":"item","numeric-id":4761670,"id":"Q4761670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e4e555f2694b701b78fdbac207839b7f80c1f7d5","datavalue":{"value":{"amount":"+0.6650064587593079","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":"Q868664$6269A5ED-CEEA-4F3A-9062-EA4A80D3B021","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:868664","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:868664"}}}}}