{"entities":{"Q2643019":{"pageid":2653762,"ns":120,"title":"Item:Q2643019","lastrevid":79112024,"modified":"2026-05-06T13:10:20Z","type":"item","id":"Q2643019","labels":{"en":{"language":"en","value":"Linear time algorithms for Abelian group isomorphism and related problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5182135"}},"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":"Q2643019$F87D4F99-C90D-48B6-8293-579783E9E442","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cd3e9d7937540cac8d8f1a3d3eed3a29b773d662","datavalue":{"value":{"text":"Linear time algorithms for Abelian group isomorphism and related problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2643019$482FFC9C-B545-47CC-A8E6-028EB1B6B62E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2304ef2a1933e274ab8f98008f3f9b4f637365ba","datavalue":{"value":"1165.68036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2643019$15CC2283-8C6F-48CE-9FF8-9E29CAB056B8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a78ba37efae866c0c500ce6e7c33dd6bef6b8d9e","datavalue":{"value":{"entity-type":"item","numeric-id":270029,"id":"Q270029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643019$4AAFEFB0-035A-4BC9-9FCC-E2A59F31FD3F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643019$5953A5E5-BE1F-413A-8392-E6C6888EBBCE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"226fad3e536b676c763bdce84a93ee9c766c4ae5","datavalue":{"value":{"time":"+2007-08-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2643019$486F1304-2558-4E4A-AB0B-4890EE6F5940","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d8b632171f2939218c55051ae2121b0669d01ed1","datavalue":{"value":"The author shows that for a group \\(G\\), given by a multiplication table, the orders of all elements can be determined in time \\(O(n)\\), where \\(n\\) is the group order. The algorithm simply powers up elements until powers are known, the linear runtime is obtained by amortization analysis. This result implies that (nonconstructive) isomorphism of groups can be tested in time \\(O(|G|)\\).   Usually algorithms for groups (see for example [\\textit{D. F. Holt, B. Eick, E. A. O'Brien}, Handbook of computational group theory. Discrete Mathematics and its Applications. Boca Raton, FL: Chapman \\& Hall/CRC Press (2005; Zbl 1091.20001)]) aim to work with a generating set such that the size of the input is much smaller than \\(|G|\\). One therefore would expect a sublinear runtime in \\(O(\\log(|G|)^k)\\) for small \\(k\\). (If \\(G\\) is abelian and given by a presentation nonconstructive isomorphism simply requires a Smith normal form computation, which is known to be polynomial in the size of the generating set [\\textit{R. Kannan} and \\textit{A. Bachem}, SIAM J. Comput. 8, 499--507 (1979; Zbl 0446.65015)].)","type":"string"},"datatype":"string"},"type":"statement","id":"Q2643019$48D4F7B1-601B-4519-A361-85F58EFA8D17","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9d1b22c512cf981f74352b0d894ac3ba97318e0e","datavalue":{"value":{"entity-type":"item","numeric-id":237007,"id":"Q237007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643019$7BD17106-1400-4951-B94D-6DC2DC924FA4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2643019$8D1F2C6E-99FB-406B-9662-E0E8908C0DE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e9b5ca6a3bce811e2a3489608b95705717ca7328","datavalue":{"value":"20K01","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2643019$FF3ACDEB-AE87-46DC-B0A8-2C2FF7950F35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f96720fe29e309c34c82deec20bd95823bb71652","datavalue":{"value":"20-04","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2643019$4430A2E7-20C1-40AB-80A8-312CF09C988D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bf3b2f07cd6dbfb78708a0ea11c36040df2c0843","datavalue":{"value":"5182135","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2643019$2C4CC049-C411-4DDD-91B5-69A618D84764","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"46ecd23792e3d388f4968cf8a692b9feb34cd0c5","datavalue":{"value":"abelian group isomorphism complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2643019$EEA4A639-D496-4CE7-B96E-25C522767D25","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":"Q2643019$B9F8C19D-5D17-456E-81D1-F206262CA3BE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2673a8e56467db00accc90bb9d254644bc52e238","datavalue":{"value":"https://doi.org/10.1016/j.jcss.2007.03.013","type":"string"},"datatype":"url"},"type":"statement","id":"Q2643019$85149395-B170-45FB-A0D8-8F286DBA1E5F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"46ae587cbcf9d070b0322b33aee602dd6435e0df","datavalue":{"value":"W2077723005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2643019$0D606703-028E-482E-ACE5-F8326E85AF3C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f82ab72024f62f8ca833e20d3b125c7cd0b2855b","datavalue":{"value":{"entity-type":"item","numeric-id":1892223,"id":"Q1892223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643019$481213FD-1AD2-488C-9138-2014AE118026","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15107e90404072bc2f562c422773cc705ca22248","datavalue":{"value":{"entity-type":"item","numeric-id":5956010,"id":"Q5956010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643019$56231A25-DCDE-4FE8-BB43-30B91167BC68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1dd6fe6e1ebd8787c08447f35a8ee943f3ea45f","datavalue":{"value":{"entity-type":"item","numeric-id":4020768,"id":"Q4020768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643019$42FB3FDD-7FB9-4481-9247-8C47BFFDF117","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95c5843cde92814bbbf9f53b408822d55a408805","datavalue":{"value":{"entity-type":"item","numeric-id":1174452,"id":"Q1174452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643019$C8B73C92-4B9A-47B2-9DAD-63092BB1D3EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5989e7b642a281e076cb0a5451b4d9c25f50f39c","datavalue":{"value":{"entity-type":"item","numeric-id":3253828,"id":"Q3253828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643019$A044D0B7-406A-49F2-84B0-138A61FEB0E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb40aa93777a7cd41d54dcf43b55867cf1b75c38","datavalue":{"value":{"entity-type":"item","numeric-id":5772619,"id":"Q5772619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643019$67FEDAC5-C4FB-4D0F-BB42-9440EE1E037C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4191320868d11d359ac895a92394db824af8152","datavalue":{"value":{"entity-type":"item","numeric-id":5733527,"id":"Q5733527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643019$0802E0E4-EAE6-4968-BECB-D73DCC23C154","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4cc83042d7191d966a185b1612b0bce2a8fe8ca0","datavalue":{"value":{"entity-type":"item","numeric-id":5191525,"id":"Q5191525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643019$482D1048-D87D-436B-B610-0409C37595A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0591227281ce1faaff610b88b4a214e8fdb32c0","datavalue":{"value":{"entity-type":"item","numeric-id":3580983,"id":"Q3580983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643019$D74E3292-5CBD-4B23-83E2-6A2A2DC03460","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aff365d8186cc4c7ca2a8c01bb1842652c3c232d","datavalue":{"value":{"entity-type":"item","numeric-id":4273947,"id":"Q4273947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643019$1590B5CF-AF4D-45D9-A0A2-A8404B22C375","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c82a636624b539fceb598818c5ef83e9599ef5dd","datavalue":{"value":{"entity-type":"item","numeric-id":5534234,"id":"Q5534234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643019$7FC155B1-AE37-45C0-B5B1-31C097CA0E0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28b517a5843fd2a87af434834e565afc127353b9","datavalue":{"value":{"entity-type":"item","numeric-id":4127386,"id":"Q4127386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643019$9F438965-51EE-44FE-A918-CEEDA9F2D340","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0154c0671b50ec0434583ab21c9846fa7528066","datavalue":{"value":{"entity-type":"item","numeric-id":5402540,"id":"Q5402540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643019$265308A0-4355-43CD-A856-E39F9713A79D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"811d62b45a33ee04d067b49bec2d40ea70684bb0","datavalue":{"value":{"entity-type":"item","numeric-id":1255944,"id":"Q1255944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643019$272B39E0-3682-4162-B954-32DBE0D616E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f807077b4188e4441802ee77fc5ab7dd646da108","datavalue":{"value":{"entity-type":"item","numeric-id":3309910,"id":"Q3309910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643019$DEEB4DF9-DAD0-4AB7-9BF7-DB1C581CC5F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1dd264c5dfd5c649381e4cc5b4c1e202d0f51399","datavalue":{"value":{"entity-type":"item","numeric-id":4317890,"id":"Q4317890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643019$1AECC563-628B-42C1-A20F-1B6621239033","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f972d0cb1c005e7331b4f43aae52c90b3b1be11","datavalue":{"value":{"entity-type":"item","numeric-id":1816737,"id":"Q1816737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643019$EEE7E0A9-6B87-4E42-8F52-2E2559BD0967","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"aaade9ff7f5b7fd1ff35b3c73aaac5968e891667","datavalue":{"value":"10.1016/J.JCSS.2007.03.013","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2643019$953C58DA-472C-4088-B5DB-213E2F29A518","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4d80ea449e5720aed869f1e0013124c92b6a5e3","datavalue":{"value":{"entity-type":"item","numeric-id":5191525,"id":"Q5191525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c4fa54941028cf5e618487d98e12bd57219da06","datavalue":{"value":{"amount":"+0.9110257625579834","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":"Q2643019$B4B528BB-BE07-46D3-A84A-D27633124F70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"52813317f753c58dbe3f23f48ee287627c982818","datavalue":{"value":{"entity-type":"item","numeric-id":1816737,"id":"Q1816737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"667e7dab48e297ff25816cc9e22204ff0376591e","datavalue":{"value":{"amount":"+0.9039860963821412","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":"Q2643019$931D57CC-AD6F-40A5-83EA-5A0A9EFD16CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c6860800f5cbf25b67b6e5f8172eb9b62e0b8da","datavalue":{"value":{"entity-type":"item","numeric-id":5918355,"id":"Q5918355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1543ce178263a3d8805289c3efc04ab7c819e8a8","datavalue":{"value":{"amount":"+0.8221179842948914","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":"Q2643019$559AC6E8-23BC-4236-8555-C74349433236","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35e89f1db4d704412c2ec065d1a5473ba8f40bef","datavalue":{"value":{"entity-type":"item","numeric-id":5919682,"id":"Q5919682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"52cdf22029e86ceafd0967885c0bfce59fc2d0d2","datavalue":{"value":{"amount":"+0.8213196992874146","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":"Q2643019$437625D0-BF0F-41A5-8AFD-2A4DD9A9CBC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"61325d4ec52c51004dee106236c40c20e06118ee","datavalue":{"value":{"entity-type":"item","numeric-id":3087971,"id":"Q3087971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"daa533b44a6b991ffe6ad01acb5f5506507ccbe9","datavalue":{"value":{"amount":"+0.8078635334968567","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":"Q2643019$99062A8B-FB17-41B0-A921-7825B092ED4C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Linear time algorithms for Abelian group isomorphism and related problems","badges":[]}}}}}