{"entities":{"Q7006276":{"pageid":21540621,"ns":120,"title":"Item:Q7006276","lastrevid":83026622,"modified":"2026-05-06T23:49:37Z","type":"item","id":"Q7006276","labels":{"en":{"language":"en","value":"Two results on complexities of decision problems of groups"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 8018283"}},"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":"Q7006276$F3E72CB8-7B3A-438F-A2F7-3BE0FEAD09C2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"23963584253947d1a4d4854925c176a20fcb656e","datavalue":{"value":{"text":"Two results on complexities of decision problems of groups","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q7006276$6CDF63D0-AE73-4D3C-8DF3-1B871B9D482D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"afd31b13365e3feea4f1c589d24d78dca151a197","datavalue":{"value":"1561.20031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7006276$D3559658-1523-42D0-A85C-BF12336B5396","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"07cdd17e90a51b8308b633b4755e483294a10851","datavalue":{"value":"10.1142/S0218196725500067","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7006276$1327988D-BAD4-4EBD-9481-96115C76D96F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8d4e8d0d40de5d64578f28267ba69171aa96f9a2","datavalue":{"value":{"entity-type":"item","numeric-id":375900,"id":"Q375900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7006276$2AAE03C9-6DBA-4460-9175-C813D1002ADD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0e5ee35daa6179cc3c1911639a50238000723caf","datavalue":{"value":{"entity-type":"item","numeric-id":256785,"id":"Q256785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7006276$DB9087E1-15A5-48E2-A5C8-23D93B49BE15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"346565cf792d4ad694685b123acb1f149c1ee36c","datavalue":{"value":{"entity-type":"item","numeric-id":1630109,"id":"Q1630109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7006276$854B6E60-93E7-47EC-A6E6-22046EA7FA3B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7f4e75461d95037e69d585d3faf5530e0368f039","datavalue":{"value":{"entity-type":"item","numeric-id":2703070,"id":"Q2703070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7006276$D13D17FD-CB59-44B8-8956-92322876D98F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"56dc2aee67e5a5f915275ac50721b545754f9aa9","datavalue":{"value":{"time":"+2025-03-31T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q7006276$1E253AC4-17FD-4C79-B4F7-382EA417BCE7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8a0fe79a48585ecda5ae7636b349d931dabf44b5","datavalue":{"value":"This article studies the isomorphism and word problems for groups from the perspective of computably enumerable equivalence relations (ceers). The central result establishes that the isomorphism problem for recursively presented groups with six generators is \\(\\Sigma^0_3\\)-complete in the ceers hierarchy, i.e., every other \\(\\Sigma^0_3\\) equivalence relation computably reduces to it. The proof uses a fine-grained construction that encodes recursive presentations into algebraic structures, which are then interpreted as groups via small cancellation techniques. This parallels an analogous result in the Borel setting: the isomorphism problem for finitely generated groups is a universal essentially countable Borel equivalence relation [\\textit{S. Thomas} and \\textit{B. Velickovic}, J. Algebra 217, No. 1, 352--373 (1999;Zbl 0938.03060)].\\N\\NThe authors also show that the set of ceers equivalent to the word problem of a finitely presented, finitely generated or recursively presented group is itself \\(\\Sigma^0_3\\)-complete. This characterizes such decision problems as maximally complex within this computability-theoretic framework, distinguishing them from earlier classifications based on Turing reducibility. The results provide a clear bridge between algebraic group theory and the structural theory of ceers.","type":"string"},"datatype":"string"},"type":"statement","id":"Q7006276$3301A5D5-16B8-4B00-91A2-0789EC7A0211","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"84143e6334371c8e3cbc935219640b812b5c932b","datavalue":{"value":{"entity-type":"item","numeric-id":258043,"id":"Q258043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7006276$79878DC4-24F6-4771-B290-13733275722F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8acfec936c9f92116ab04a417b25b0b6b0e8ab90","datavalue":{"value":"20F10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7006276$B1CA6272-DC0B-4B89-810D-DF0F31412BC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"379be2ae88ac653823960287ba517e23fc9265f4","datavalue":{"value":"03D30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7006276$8CDA0BFA-CA33-42DA-9488-0881317AE52A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3fca415580115e1e0a74c69afb3a7d85b0c01d8d","datavalue":{"value":"03D55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7006276$3D05D906-94E6-4CE8-98BC-CF8BA32D4023","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f5446682a305204b1befda53f46d7d74c1133430","datavalue":{"value":"8018283","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7006276$4EEF3D7C-90D6-4D03-9D5A-15EAB1EBC1AA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"541e14ca1a9bb27a1cfe827610ca5ddb594a16de","datavalue":{"value":"word problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q7006276$833D340E-DD6C-4E03-AD2C-F6A755DCFAD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b181606adcba6432b0019d481c67f516d9807857","datavalue":{"value":"isomorphism problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q7006276$0DE57F84-B82E-4821-8EB7-890AD6895868","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6ff39eb813fd07173d2b73033b13894cfdfb71e0","datavalue":{"value":"computably enumerable equivalence relation","type":"string"},"datatype":"string"},"type":"statement","id":"Q7006276$119D565F-E02B-4E28-96EE-678E82524680","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":"Q7006276$BA3EF108-3E32-43C1-8C78-DEBCD1D2EE06","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f37f085b7a9beafb4a4c46af1ed41888dc503dc2","datavalue":{"value":{"entity-type":"item","numeric-id":5848908,"id":"Q5848908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7006276$6DB899F5-24DC-4765-8232-EFC243A7A2FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73964244b50ac6a01b3bd24fccdbd805ad86369c","datavalue":{"value":{"entity-type":"item","numeric-id":2970971,"id":"Q2970971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7006276$116AE09F-E4C2-4B52-9615-2393E85CF958","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11e960618f63ae42a913c15d0d8d824752583a07","datavalue":{"value":{"entity-type":"item","numeric-id":2921020,"id":"Q2921020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7006276$FD03E567-B016-4E8A-9E0D-4CBFA48FE68F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c06266d6fcc8a50b028f231c1d622a73660326f6","datavalue":{"value":{"entity-type":"item","numeric-id":6967218,"id":"Q6967218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7006276$67DD9489-9698-49A1-A315-C4402072250D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0167b4c7e4e139b401aae803a2e6f3403d5e1f81","datavalue":{"value":{"entity-type":"item","numeric-id":2976337,"id":"Q2976337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7006276$FC923998-DD81-4FF2-9C3C-EC42ABFC798C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"47291d02906a7ba93701591e5c7e50238969803a","datavalue":{"value":{"entity-type":"item","numeric-id":1693042,"id":"Q1693042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7006276$BD44D6D0-3F8A-426C-BB27-F7652889506C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37648fc19e9052ac48d4c653c04d45b8be15c335","datavalue":{"value":{"entity-type":"item","numeric-id":5211062,"id":"Q5211062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7006276$0415BD4D-1469-448A-8B9D-0011CB3E7860","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33416ed4278ac415972947aba7ea623f89a2c8ed","datavalue":{"value":{"entity-type":"item","numeric-id":5583068,"id":"Q5583068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7006276$334B0D47-327C-40A4-887F-95D1AA50D67A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a41a23cfcd5e44f329acc4abc0eefe53035ea6cf","datavalue":{"value":{"entity-type":"item","numeric-id":3228627,"id":"Q3228627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7006276$F79AE680-4CF7-4D14-AC7A-427974981FD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12d3b9df719966b3a6d2f65c68f77c792bc376bf","datavalue":{"value":{"entity-type":"item","numeric-id":2531870,"id":"Q2531870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7006276$C4A94BA8-AF69-4552-8EC2-1622CB4123B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6939b7c6b5e1e43a2947e6d05e58171b2f424c55","datavalue":{"value":{"entity-type":"item","numeric-id":3934450,"id":"Q3934450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7006276$5686B9B3-CD00-4AC7-9F04-EFE87F7EF562","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da3b2f55bc190ad796e7940c53e0ca768a0843f8","datavalue":{"value":{"entity-type":"item","numeric-id":5639879,"id":"Q5639879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7006276$05A76269-6CBF-47C8-A626-04A38A35D675","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"47f038f190189729a61fb14e7c25099f135a0c26","datavalue":{"value":{"entity-type":"item","numeric-id":1483698,"id":"Q1483698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7006276$9C27C81D-6DD9-4FBF-9FC3-AF8C73F38FB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42cd6764e318607d903b0dbce1af590b8983a2a1","datavalue":{"value":{"entity-type":"item","numeric-id":5601472,"id":"Q5601472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7006276$B65D85FC-BFA8-4C9E-9F90-9A63C72D6B3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59e2ecee767e81da56034513cc44b906e0cf609b","datavalue":{"value":{"entity-type":"item","numeric-id":5939996,"id":"Q5939996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7006276$713DCE08-BB58-49E3-9597-0945A2941890","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc23cfb6c51cf974e3d518475165736beb7cab29","datavalue":{"value":{"entity-type":"item","numeric-id":2003917,"id":"Q2003917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7006276$83DF85D1-60D3-40E6-ACA3-1800B947CE52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee32fd238cd7aa72816d70e40416ef162832c6ee","datavalue":{"value":{"entity-type":"item","numeric-id":3288145,"id":"Q3288145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7006276$4AFA8BC3-27B7-4FBB-BDE6-FEE70C448849","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23a52c26566fec192c01fbc25554a5255473b2a5","datavalue":{"value":{"entity-type":"item","numeric-id":4402143,"id":"Q4402143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7006276$A11FFA03-8C2B-4158-AD5D-92D36FD1A499","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"414a8da8e3f49dd259f5319eb52852cbcc99d052","datavalue":{"value":{"entity-type":"item","numeric-id":768811,"id":"Q768811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7006276$D48B675D-2788-4821-A7A8-FAEBA1CA30C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05546921da427e4e9ae4308509db78b99b42c985","datavalue":{"value":{"entity-type":"item","numeric-id":6116397,"id":"Q6116397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7006276$967E86D9-43B3-4CCB-9E16-3C4AC79DC186","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"340c3e41179e1a9930fbf5108bfe11ef22906947","datavalue":{"value":{"entity-type":"item","numeric-id":1305085,"id":"Q1305085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7006276$03DF152F-CDB5-4BF2-8949-BAE53A42E3AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6481b3e4581dc07adfa244bd052d58630243f76d","datavalue":{"value":{"entity-type":"item","numeric-id":4140977,"id":"Q4140977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7006276$B7A3C52A-71A0-4BF2-9DA9-9C8CFACF0DA4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Two results on complexities of decision problems of groups","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Two_results_on_complexities_of_decision_problems_of_groups"}}}}}