{"entities":{"Q1177176":{"pageid":1187925,"ns":120,"title":"Item:Q1177176","lastrevid":66769029,"modified":"2026-04-12T12:43:42Z","type":"item","id":"Q1177176","labels":{"en":{"language":"en","value":"The complexity of Grigorchuk groups with application to cryptography"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 20026"}},"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":"Q1177176$33730FDD-850F-4D75-8E03-9661EEF03894","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ab905cbb6a22f70b34d6db6ba827c25d54d89f3a","datavalue":{"value":{"text":"The complexity of Grigorchuk groups with application to cryptography","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1177176$D014DDAC-8E3B-440E-9987-D6429EE234F7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3bfbb2d7e9ff5bcea0b4fc89be13459658a2f1fd","datavalue":{"value":"0749.68040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177176$739006AF-F799-4A8C-98C9-041FAD9EC820","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"16ae14c0e1957bbf176ea14795e43bce8d543b3e","datavalue":{"value":"10.1016/0304-3975(91)90074-C","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177176$E1F8D4E9-64FD-4780-B765-4599B7DB338D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"10dab932582be780d68eb0ec58722147c268756d","datavalue":{"value":{"entity-type":"item","numeric-id":579425,"id":"Q579425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177176$C1C575C8-B891-4EE8-9FB0-04ABB2046177","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7dec9c274675ab1cf3162789e1a3526ee1820da9","datavalue":{"value":{"entity-type":"item","numeric-id":702491,"id":"Q702491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177176$9B69A0A9-A132-4835-AF0C-100AEFF2167C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177176$D21A51EF-7D5C-44A1-ADBC-FD7029E70A36","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1422b5e3113eee9dc98f0455d275631058399b8b","datavalue":{"value":{"time":"+1992-06-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1177176$86ADEF6F-46ED-4401-9C56-64E3056DC1A0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"daee934b146d50503deba16d16bcf7e74ef4e739","datavalue":{"value":"The complexity of the word problems of a class of groups introduced by Grigorchuk is examined. The Grigorchuk groups are natural families of groups of automorphisms of a complete infinite binary tree defined by means of a special general construction to transform any one-way infinite sequence \\(\\gamma\\) into a word problem of a 4-generator group \\(G_ \\gamma\\) of level preserving permutations of the infinite complete binary tree. It is shown that the word problems in Grigorchuk groups yield natural complete sets that separate time and space complexity classes if they are distinct. New families of nonfinitely presented groups are shown to have word problems uniformly solvable in simultaneous logspace and quadratic time. An interesting application of the results is that a new family of public key cryptoschemes can be created. This is pointed out.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1177176$C7CD0DBF-A6B7-4661-BA11-4A6B4AE47E13","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177176$7810FE54-6CC2-41BD-80FE-B2D4AF814C11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8acfec936c9f92116ab04a417b25b0b6b0e8ab90","datavalue":{"value":"20F10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177176$784C8DF7-52C4-41A2-83EE-A6BD10E1144B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177176$A997C205-8B0D-4188-AED8-BDEEF02F2593","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177176$A7F14BA4-0B99-46C9-9658-B29AD2AAB83B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"58bd804a9b32ab16fea71636cf187b83a20de8f7","datavalue":{"value":"68P25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177176$707EC48D-F6F3-485A-BFC8-BA7868C0CE26","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f9564d9b01b37555c88b6cee98d34fa7ab8856c3","datavalue":{"value":"20026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177176$0B37751B-BCAD-411D-8E2E-1008D17B218A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4ba259c5c06af63100955fccf8bc8b370e89eaee","datavalue":{"value":"word problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1177176$9DD2755A-9C36-4B59-B4A7-84769D558B6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a3aad53c67c9eb84b8de2fc788aa09e5caff855d","datavalue":{"value":"Grigorchuk groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q1177176$EFD1AF1A-E448-4E3F-8E9E-4E4F3D62853E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"97e2434a907c69c325f5ee3a84cdd55deb12717f","datavalue":{"value":"public key cryptoschemes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1177176$0176B8B0-BB54-456C-9641-5C802BFB584C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"377196f0936f14c5f40316c205cbb7535714207a","datavalue":{"value":{"entity-type":"item","numeric-id":585662,"id":"Q585662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177176$2917711D-A6CD-4D97-820D-A1F552A0742D","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":"Q1177176$0C574840-BC94-41AA-ABF1-9AAC0D077740","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ea830727e9b6bedf20862785e40529682d300fc","datavalue":{"value":{"entity-type":"item","numeric-id":5652216,"id":"Q5652216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177176$19D3E65F-24FC-4580-BD8D-8F0904CA76D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cc6c6b83abc176e315c7d71e3791c8be4b4af07","datavalue":{"value":{"entity-type":"item","numeric-id":1243274,"id":"Q1243274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177176$024A8FE3-2610-4406-B0D6-9213D5B60247","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c4b58f9e8478a4210509de111b81e4ccd911506","datavalue":{"value":{"entity-type":"item","numeric-id":4086709,"id":"Q4086709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177176$D691F7B9-98E7-4E4F-B777-141FC962D6F0","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":"Q1177176$6187E6E9-40D1-46DB-A243-C2ECB29B6732","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64eaadb5fe90b853b5422ea4979121c326763206","datavalue":{"value":{"entity-type":"item","numeric-id":1062144,"id":"Q1062144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177176$BB4A0488-9415-4CEC-B49E-C9C9B4CCB7DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3497db5359ece7d4216c59ca6d19d212a1a4e73","datavalue":{"value":{"entity-type":"item","numeric-id":3708192,"id":"Q3708192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177176$1455B0DF-1AEE-49CE-8091-A1F24DB7ACB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177176$B2DD8288-9FDF-4680-A99D-21E7F079A72E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3abf6cc0c3833a65cd151988fd2aed2ebfc75569","datavalue":{"value":{"entity-type":"item","numeric-id":3957135,"id":"Q3957135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177176$17EC594C-AD8A-4BC4-9751-10E5C63DA066","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"175989e512d6162d2e23de4539fb227c102249ff","datavalue":{"value":{"entity-type":"item","numeric-id":4131647,"id":"Q4131647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177176$E69B03D6-77E0-410C-8671-1AA584B6A5D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82d3cbffed8a301b84b1253490d8c6b17bf2e322","datavalue":{"value":{"entity-type":"item","numeric-id":4145882,"id":"Q4145882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177176$BA8BFED3-615F-4042-8EAD-C2A575EFD96A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54dd7be43df6443b39096d1271d01a6a5f04b2e6","datavalue":{"value":{"entity-type":"item","numeric-id":3787915,"id":"Q3787915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177176$F3FCEB83-F0F1-4263-AEF2-0E35B3BAFE8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2af188522ee36dfbc40e8063345c06265fc901ae","datavalue":{"value":{"entity-type":"item","numeric-id":792454,"id":"Q792454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177176$1BDFF91D-7DA7-45E0-8ED1-AC1739D013E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"736a1d463d18d2f300e2b9600c3f86eae2986ef8","datavalue":{"value":{"entity-type":"item","numeric-id":2537313,"id":"Q2537313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177176$9965B8B7-B3E1-4F4A-BFA5-9F1FDFBA997D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92dbd271da4abb6503ed890a2ba31e5fffa0b9d5","datavalue":{"value":{"entity-type":"item","numeric-id":3048248,"id":"Q3048248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177176$83F1A325-0539-4063-97EB-CEC45840283E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2bc96eb9c9ec47ba72af3c7e9ef7a87792f88799","datavalue":{"value":{"entity-type":"item","numeric-id":2552199,"id":"Q2552199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177176$7E1B58B0-C0F9-4DF9-8059-A7CA8CEF684D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6292bcb79b495d2870792ebae51f5161a90ba63a","datavalue":{"value":{"entity-type":"item","numeric-id":3657450,"id":"Q3657450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177176$C26FFC1E-4617-4EAF-984B-BC2C3A7BA5F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09454a504939a037e0ba2c87d5e1790874648f21","datavalue":{"value":{"entity-type":"item","numeric-id":4085717,"id":"Q4085717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177176$55CE02FA-F681-4AC5-A5A1-F83BF0B87993","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"652a09ae5013ee39debc1ba68c1b920b7edf6172","datavalue":{"value":{"entity-type":"item","numeric-id":3962990,"id":"Q3962990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177176$6D26C027-F994-41F2-A0C3-61EBFCBDABBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebd279198677644f2d5ced4d4655a2346da12e46","datavalue":{"value":{"entity-type":"item","numeric-id":3688303,"id":"Q3688303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177176$0241385D-7391-4935-BE0E-A65F7F48E0E4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"499bee36bf4714ffd4a38fe90dfbf0fdf323e647","datavalue":{"value":{"entity-type":"item","numeric-id":5428166,"id":"Q5428166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff16937e9c04b25c858db147e440eca30a91cdbb","datavalue":{"value":{"amount":"+0.8676491379737854","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":"Q1177176$07C758FB-6506-4142-BD98-E3269B9BC875","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1748c179ee88830f6d737417092adaab7b4e12e3","datavalue":{"value":{"entity-type":"item","numeric-id":3101433,"id":"Q3101433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4360bcbf17e4ad2489648104975d6596d37eb382","datavalue":{"value":{"amount":"+0.7909128069877625","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":"Q1177176$F9EDE15D-3FEB-4E7E-A347-507DCCACF402","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df298f020f77e65ac8de5c9fb4cf9481a6ea3171","datavalue":{"value":{"entity-type":"item","numeric-id":3688303,"id":"Q3688303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0cb10a057cbd2e2d877fd14f583d4426543ab4a2","datavalue":{"value":{"amount":"+0.7847040891647339","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":"Q1177176$F89C81D3-2544-4EBE-B32E-6A77921D27F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22c84fef84b23488e9175ff68de96ca9fa4c334d","datavalue":{"value":{"entity-type":"item","numeric-id":849353,"id":"Q849353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19c41ceab0dbc5bfb47442c7f4b298b8da1f2c41","datavalue":{"value":{"amount":"+0.7833922505378723","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":"Q1177176$F45564E5-2879-469C-A3DB-D6FA2242693B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5cf29615696a930fc67431439941acd17dcf642","datavalue":{"value":{"entity-type":"item","numeric-id":1877355,"id":"Q1877355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c899d58f421d781ba7bf1d25a757534f9a2e08b","datavalue":{"value":{"amount":"+0.7825399041175842","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":"Q1177176$176DD06B-3A75-4F12-BA2E-2E65532779AF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The complexity of Grigorchuk groups with application to cryptography","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_complexity_of_Grigorchuk_groups_with_application_to_cryptography"}}}}}