{"entities":{"Q1399190":{"pageid":1409930,"ns":120,"title":"Item:Q1399190","lastrevid":67350189,"modified":"2026-04-12T17:01:55Z","type":"item","id":"Q1399190","labels":{"en":{"language":"en","value":"Generic-case complexity, decision problems in group theory, and random walks."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1956756"}},"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":"Q1399190$A36A3934-9F39-4CE5-B1C7-D03939BF330B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"74010e9166ef618da1477ff9a8d728bc85140c39","datavalue":{"value":{"text":"Generic-case complexity, decision problems in group theory, and random walks.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1399190$9E69046D-C82F-4EA0-9277-6522A21AC21F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"adcbbfdb07c51036df0f582a9a3282b166b74ab9","datavalue":{"value":"1041.20021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1399190$063694D3-195B-4386-8F8B-8951A081CDBD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0c46bad78bfe273eb4ad52f7b719fa24725a583c","datavalue":{"value":"10.1016/S0021-8693(03)00167-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1399190$D8FED4D4-8777-46D5-9BE9-8B1848849B58","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"05ac1b58b41c5d2f6f6e0917d3815729a0d983cb","datavalue":{"value":{"entity-type":"item","numeric-id":185602,"id":"Q185602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$5C1AD05D-1CFE-4BED-93B8-97AC2CF65868","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"32ef2a6b40d2811e6e5e28e955b133457a132137","datavalue":{"value":{"entity-type":"item","numeric-id":201443,"id":"Q201443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$C263B3A5-2E56-4A58-AAC1-C04F9C8E7B82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2b1843ff51384642f69cbb6cac945664c66fbeb9","datavalue":{"value":{"entity-type":"item","numeric-id":639687,"id":"Q639687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$D0B6F676-0F44-42BB-A6EA-9F0CA94A17DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"698bc4fe65f79b85d517df655a1aca4a01c66cfe","datavalue":{"value":{"entity-type":"item","numeric-id":444387,"id":"Q444387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$A50CA309-9C59-41EB-BEA4-01DFC02D5A83","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"93541bb195a0809b1f249396bcebe99d047e6b6c","datavalue":{"value":{"entity-type":"item","numeric-id":161561,"id":"Q161561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$60474499-4BA6-4B1C-960B-12A2D07D211E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1395e3cd70742e731c96f59db982fc04f0d8f93d","datavalue":{"value":{"time":"+2003-07-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1399190$52135764-F453-48CD-AF51-351F30192031","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3b984f24d90a256ccbe825abebcec689ebab1280","datavalue":{"value":"https://arxiv.org/abs/math/0203239","type":"string"},"datatype":"url"},"type":"statement","id":"Q1399190$0A89745F-DBCA-4878-9860-EC5A374A7783","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d2b2b1af9b88c2b5ff716edc01e7920fdf4eec7c","datavalue":{"value":"The authors suggest a precise definition of generic-case complexity of a decision problem in group theory and show that for a very large class of finitely generated groups the word, membership, and conjugacy problems all have linear-time generic-case complexity. The idea of generic-case complexity is that for some decision problems (which may have high worst-case complexity or even be unsolvable) there is an algorithm which quickly produces a solution for ``most'' inputs of the problem.   For a set \\(S\\) of \\(k\\)-tuples of words over a finite alphabet \\(X\\), let \\(\\rho_n(S)=|S\\cap B_n)|/|B_n|\\), where \\(B_n\\) is the set of all \\(k\\)-tuples of words over \\(X\\) of total length \\(\\leq n\\). The set \\(S\\) is called generic if its asymptotic density is 1, that is, \\(\\rho_n(S)\\to 1\\) as \\(n\\to\\infty\\). If, in addition, \\(\\rho_n(S)\\to 1\\) exponentially fast (which means that there exist \\(C>0\\) and \\(0\\leq r<1\\) such that \\(|\\rho_n(S)-1|\\leq Cr^n\\)) then \\(S\\) is called strongly generic. Let \\(\\mathcal C\\) be a complexity class (e.g. linear time, polynomial time), and \\(G\\) a finitely generated group. A decision problem \\(D\\) for \\(G\\) is defined to have generic-case complexity in \\(\\mathcal C\\) (strongly in \\(\\mathcal C\\)) if for every generating set \\(A\\) of \\(G\\) there exist a correct partial algorithm \\(\\Omega_A\\) for the \\(A\\)-version of \\(D\\) and a generic (strongly generic) set of its inputs \\(S\\) such that for any \\(\\sigma\\in S\\) the algorithm \\(\\Omega_A\\) terminates on \\(\\sigma\\) within the complexity bound \\(\\mathcal C\\).   Here are the main results of the paper. Suppose \\(G\\) has a finite index subgroup \\(H\\) that possesses an infinite quotient group \\(\\overline H\\) for which the word problem is solvable in \\(\\mathcal C\\). Then the word problem for \\(G\\) has generic-case complexity in \\(\\mathcal C\\). Moreover, if \\(\\overline H\\) is non-amenable then the generic-case complexity of the word problem for \\(G\\) in strongly in \\(\\mathcal C\\).   The result is applicable to a broad class of groups; in particular, one can use that the word problem for a word-hyperbolic group is solvable in linear time, the word problem for a linear group over rational numbers is solvable in cubic time, and that any group that embeds \\(F_2\\) is non-amenable. A generalization of the result to the membership problem is given. Also, it is shown that if \\(G\\) has infinite Abelianization then the generic-case complexity of the conjugacy problem for \\(G\\) is linear time. The proofs are based on the known theory of random walks on regular graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1399190$34A4F812-6859-40D4-8B43-1ED4A4432631","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8acfec936c9f92116ab04a417b25b0b6b0e8ab90","datavalue":{"value":"20F10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1399190$375C5715-2E00-45A9-972D-6C74AD60BD84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1399190$ECB15E12-DBBA-4220-B138-3DD7D49C134B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e52a86b600bbb05d9a7823bf91d423713b4b70ab","datavalue":{"value":"60G50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1399190$1BF78C75-58A9-408B-ABB2-F74059FE9C6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1399190$56BAC950-DB3E-4084-97F7-6ACBC40E41FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1399190$D6BFDB26-5D6B-491E-BF25-166CE318E666","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5608e4dbe85e8f6c220cc8afcea2a4ada066e3fa","datavalue":{"value":"20F05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1399190$0A3A689C-F274-4FC6-AA7B-DD562E814135","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ea37469d91f3037e8b6809fc66f770f1b27a461d","datavalue":{"value":"20E07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1399190$1DA8EAF4-FB30-4BF6-8E72-93092D5F81C4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ad75e165a099a313e439a8a779ac379fa9ab7a21","datavalue":{"value":"1956756","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1399190$F8D5BA59-5841-4983-8F6A-036A2D82F088","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88131009e873277adebb4917fd6a91e2a43129ad","datavalue":{"value":"decision problems in group theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1399190$C02FF6E1-759E-4C0E-886A-2647AB87302C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"541e14ca1a9bb27a1cfe827610ca5ddb594a16de","datavalue":{"value":"word problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1399190$0F25EAB4-AAB3-4174-8744-B4E4A4A61F67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a2a5aaf2813613e191091bab6a7937bd2f6db3d","datavalue":{"value":"membership problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1399190$604C4CDB-FA8A-438C-8912-C209E6479CB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3a63ee56c4d2f81c4a9b7f5e8124d077a3591e1b","datavalue":{"value":"conjugacy problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1399190$1397F2CD-C5EC-4DBA-B0CD-513DE782DDBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"525586f7f0852d84a5b56ad455da977a4639d4b5","datavalue":{"value":"generic-case complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1399190$F4C81927-1E5A-4258-A7B0-16C012889801","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c84fc0d37b81c48fac237170dfbe1ece56cb50e3","datavalue":{"value":"random walks on graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1399190$29149A2C-580D-4B06-9F8E-E6097EFE1AE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"542470d6f63fefcd2ae937cc78d1c833a1db112c","datavalue":{"value":"finitely generated groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q1399190$94C234E7-26D5-4D43-8EB9-D04DB8653291","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d7a760754899c4252076421c1bbdd70a575016d7","datavalue":{"value":{"entity-type":"item","numeric-id":593287,"id":"Q593287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$7E41D0B1-99E5-4394-953D-EF3A83CA2930","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"c28ed0acca7fa569ca8dcea5ef65909cb12441fd","datavalue":{"value":{"entity-type":"item","numeric-id":16459,"id":"Q16459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$9D7A8F28-7CE4-4C8B-979E-B9FEF70B8287","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":"Q1399190$D0C1DECE-ADA6-4FE1-BDDA-293C874F20BB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ffed4a264e02b8ca38a9036bd3449d8c1e36a4f","datavalue":{"value":{"entity-type":"item","numeric-id":4515867,"id":"Q4515867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$D88ABEC2-2B2C-4CB5-BE92-6E7CCFB936E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5127d328e7f6b33db98bd0ccbe9cf299bcd9f6e7","datavalue":{"value":{"entity-type":"item","numeric-id":4865833,"id":"Q4865833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$50552BA6-F88C-4DEE-88DB-088A94C0843E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d69b809aabfb27b55e332e5731e4638ab132539","datavalue":{"value":{"entity-type":"item","numeric-id":1574733,"id":"Q1574733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$A3919F5C-FC6E-4CFA-ACD4-25B84947EBC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c858629afcf6a8a06c5e2e05a906423e4bad1e59","datavalue":{"value":{"entity-type":"item","numeric-id":3718927,"id":"Q3718927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$8597F5AC-50B8-48C2-AB95-742D8235BA37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2891be9e3d003a28058c1a06e670d14248a4db80","datavalue":{"value":{"entity-type":"item","numeric-id":791646,"id":"Q791646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$3F979B02-A323-4D4D-80A0-A4778E748531","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"526d1a28509315e8c3b9e0d6edb5cb554c454360","datavalue":{"value":{"entity-type":"item","numeric-id":1358513,"id":"Q1358513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$DF56BD56-9395-429C-9BB0-F40222D13C1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c484e99e7d2206202e91cc31c2094e4d7a6049b1","datavalue":{"value":{"entity-type":"item","numeric-id":4257100,"id":"Q4257100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$9DCC40BA-1ED3-4424-A696-F934B022C216","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5552ed20a0e5d9a507a3c8fe87c56451f19dff8f","datavalue":{"value":{"entity-type":"item","numeric-id":4216832,"id":"Q4216832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$BBCE03A1-B534-4058-B9ED-CBCE6601EC31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c2f397f99118e5c97df7f2512cb4081371f48b2","datavalue":{"value":{"entity-type":"item","numeric-id":4505871,"id":"Q4505871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$B49B800C-2338-4919-971C-525334D93405","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84c40aaaafb858dbf8fc433929ed7a1845e11c1e","datavalue":{"value":{"entity-type":"item","numeric-id":1594949,"id":"Q1594949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$21C08895-07BE-43DB-8533-1FA20F7B72B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe8fa3bb038a8ad0faf0dcfff21acfb0df29f13d","datavalue":{"value":{"entity-type":"item","numeric-id":4169053,"id":"Q4169053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$B8FF297C-E751-4AAF-B1E0-E785F5EA939D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8428f9b1d017c23be63e820c9b20c9335447de1d","datavalue":{"value":{"entity-type":"item","numeric-id":1183379,"id":"Q1183379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$0FFBB71A-E957-4B25-ACC8-221AA544C185","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e311c708512c4fb0c51de3f2fc86aec5ade32820","datavalue":{"value":{"entity-type":"item","numeric-id":4335289,"id":"Q4335289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$34CAA801-0139-40CB-B85D-131A49EFB766","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0854ffba55913ad2a7ece15cb79fd713df28328a","datavalue":{"value":{"entity-type":"item","numeric-id":1273842,"id":"Q1273842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$1306A85C-444E-4B6A-B15E-B6AC971F7D25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4bd9649bb35950bb7c226813470b8085926566c5","datavalue":{"value":{"entity-type":"item","numeric-id":4469600,"id":"Q4469600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$C5633597-3688-4215-8668-D8EE07056FF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4307c19a0f362d478f0d172e29693d23935bb8b0","datavalue":{"value":{"entity-type":"item","numeric-id":4781979,"id":"Q4781979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$2B547361-EDBC-40D6-BB68-5D1F77AAC610","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1258201292f987796b37ca73483d9fd56c177d4","datavalue":{"value":{"entity-type":"item","numeric-id":4518103,"id":"Q4518103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$D7AD26B5-0A18-4CE1-A660-347C54559A17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9cd40d6cd6030a671c191205c191d2354c1060d7","datavalue":{"value":{"entity-type":"item","numeric-id":1332129,"id":"Q1332129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$9872FFFB-4877-4678-B680-F9B5A627C569","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1afecf2da27b82df16e7cc2f803a52bb0cbeaf68","datavalue":{"value":{"entity-type":"item","numeric-id":1910397,"id":"Q1910397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$9C1F2750-3964-4B0A-9533-ABA88EA0D656","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8eda13d166ba3560df014dfa8e2c32cdbfd63de7","datavalue":{"value":{"entity-type":"item","numeric-id":1568682,"id":"Q1568682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$5876AA69-1F77-4F2C-B3CC-36649AC19BFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c78890a456628b4f1bbaff32d94b1334ba047acc","datavalue":{"value":{"entity-type":"item","numeric-id":1816507,"id":"Q1816507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$2B924D9A-8125-4DA8-95F0-712B4824242B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bffbcbafc9de9423bf58a1eaef908e24d0cd215","datavalue":{"value":{"entity-type":"item","numeric-id":1594922,"id":"Q1594922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$7019CE84-DE61-4498-BB6D-C5A24F9B830F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"038b744b56bcfd10d68f981134e4f5cff73802bd","datavalue":{"value":{"entity-type":"item","numeric-id":1171646,"id":"Q1171646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$3E4829FD-EF69-4C4B-A0BB-A2DB863ACB96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b0fdbf63c06daffbf0c14626d27f5b03f4a3768","datavalue":{"value":{"entity-type":"item","numeric-id":1188860,"id":"Q1188860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$80E27AD6-4E66-44EC-8621-23712B1778C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac593b8d844f289785c5bca4b3e44139f06bd56b","datavalue":{"value":{"entity-type":"item","numeric-id":675872,"id":"Q675872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$6414EC8A-35BD-4AC2-8709-FE7F88B2249E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bda3489b46b03cce2e2d044b296bd7198c95bbca","datavalue":{"value":{"entity-type":"item","numeric-id":4003861,"id":"Q4003861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$50FCB7FD-4B06-49B7-9BC9-3142F927B9E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1d40935f959c541083294ae81e1129c6ff6ba69","datavalue":{"value":{"entity-type":"item","numeric-id":1803625,"id":"Q1803625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$D7E22482-0FAF-45E3-86AB-213EFF8E5A60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dfdeb15cdf1f7ead0a1baeb3f00e40c6189b6b8a","datavalue":{"value":{"entity-type":"item","numeric-id":4240567,"id":"Q4240567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$1AED0EF3-C6B2-4606-8356-F55B9EC2506E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f1b57f281e089d752f83218a3b45aa343c430c9","datavalue":{"value":{"entity-type":"item","numeric-id":1177434,"id":"Q1177434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$BD4E0A39-004A-460F-A841-3B9EF2794D12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5230d0e23530a08a106d3f1738ba394b1f7741a3","datavalue":{"value":{"entity-type":"item","numeric-id":1188934,"id":"Q1188934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$C79E40F5-FB07-495D-99E4-87CEA398408C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32bc49bb1412faf1d4d3e2aac0c1dfed12aeffe7","datavalue":{"value":{"entity-type":"item","numeric-id":3930365,"id":"Q3930365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$84A719C2-13F6-40AC-9C4D-A36AA7EBDB78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"320a4959b3b19951cebc6a79a1a4b49c7a726972","datavalue":{"value":{"entity-type":"item","numeric-id":3772406,"id":"Q3772406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$604812FA-959D-4E2D-B68A-90303D496B02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2fde7e79cb1dee2c5a78cce3ac4d49dcd1f6f4e","datavalue":{"value":{"entity-type":"item","numeric-id":1176231,"id":"Q1176231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$13264F53-ABDD-4EB8-826C-A00432BF11BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99cb5f8821cd28ee9eb0d775b75c206e0baa2f84","datavalue":{"value":{"entity-type":"item","numeric-id":4786246,"id":"Q4786246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$4524D1CF-3167-4F89-AB28-8B26E2C37FBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df3f2a1c1d1c86956dec0d1f866fb5a4841006d5","datavalue":{"value":{"entity-type":"item","numeric-id":3151018,"id":"Q3151018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$28EB8054-392E-4AA4-967B-986D5C541A64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c7c667bd75cdd3304eec99136ae018b925f2e19","datavalue":{"value":{"entity-type":"item","numeric-id":1419582,"id":"Q1419582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$4C4B7315-F783-40DE-9FE5-2D313B706F71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88c255f2e6ecd34a611f1ccf928bf197acbeea63","datavalue":{"value":{"entity-type":"item","numeric-id":4051879,"id":"Q4051879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$FCDE5FDB-0EAB-40EF-AD13-02696B546C97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04533b5e4f54e7a61c4fc1c55a4a47c19e20f43a","datavalue":{"value":{"entity-type":"item","numeric-id":3718151,"id":"Q3718151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$5EF4EAFE-3073-4300-8FAD-9FD2E349E6F3","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":"Q1399190$170C92EC-2CD0-4B03-8141-3CF660D0D6B4","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":"Q1399190$11B71360-E746-4AD6-BAF4-6E674459B430","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"237c684ef2edcf9081c7d150999c7a70ce33f879","datavalue":{"value":{"entity-type":"item","numeric-id":3252716,"id":"Q3252716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$160CEC29-539D-4198-8783-FC20531AC30F","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":"Q1399190$0AD29D68-569B-421C-8E85-000C76FD5BA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ffab9107d6323d7b497634ac7635a953e1d2932","datavalue":{"value":{"entity-type":"item","numeric-id":4012134,"id":"Q4012134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$7B35B78A-BC91-4CAE-A5C2-AB5AB755065D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64efc6e2d0423fd507b2505eebdd36de51588b62","datavalue":{"value":{"entity-type":"item","numeric-id":4024644,"id":"Q4024644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$0F38FFCC-E00B-49D6-A900-DD718E5E7CA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3479b1b8ce1eb8a8699c52a172d26d4d947366b0","datavalue":{"value":{"entity-type":"item","numeric-id":4298260,"id":"Q4298260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$D4AF8051-D4A0-4795-8D7B-24B8134931F4","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":"Q1399190$2045C9FA-D74B-4B98-8F6B-121EA453907E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4783b2ffdfe1c9fe791f77fe416f07d46a62f5dc","datavalue":{"value":{"entity-type":"item","numeric-id":1868437,"id":"Q1868437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$5015877B-B92F-4F71-89B7-319ABB0A0F4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f12bfc7fe7fce4971e4c4678955239088fe23569","datavalue":{"value":{"entity-type":"item","numeric-id":3123638,"id":"Q3123638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$1D3E72C4-0C53-42F8-B50F-82B16AB4F4B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"decbfc2fc7f61ae1d852a2be1b9e7ba4fae2cc61","datavalue":{"value":{"entity-type":"item","numeric-id":1323108,"id":"Q1323108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$247BF02B-0BC7-41D3-A8D0-AB22EE93FA3D","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":"Q1399190$9D94FAD9-D5F2-4F84-B6CA-22B8A81CC723","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ec7bc327aaf3fd0f35a210ad4140945e52ba90b","datavalue":{"value":{"entity-type":"item","numeric-id":2710707,"id":"Q2710707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$FD1C63B5-534C-45D1-90CC-BC52502B0201","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":"Q1399190$7D19E5A8-4BC5-4763-8B88-84EBC1342BD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1165bc598ddf6309079f75a261e98277fe6229b8","datavalue":{"value":{"entity-type":"item","numeric-id":4234079,"id":"Q4234079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$A4477509-1DF1-4581-9800-C262D87DBFB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7edef037be0ae2b79df7523cd4b89a3d242b4d71","datavalue":{"value":{"entity-type":"item","numeric-id":4359465,"id":"Q4359465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$0FFC4CBD-8B07-45F0-AB33-A2659BCBFD33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a127b919f9347dc7b29fecd4dc7a83c823ad2e18","datavalue":{"value":{"entity-type":"item","numeric-id":4268708,"id":"Q4268708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$F6A38B46-9D1A-4439-8948-79A145319C59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d19a08a321375db58ff4b743a6f8ec172be82389","datavalue":{"value":{"entity-type":"item","numeric-id":1055896,"id":"Q1055896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$8E35D1F9-78BA-4848-B0AC-D28D4DE8ADEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29a08192d2b763a809fa84089dcb104d286c605c","datavalue":{"value":{"entity-type":"item","numeric-id":4289472,"id":"Q4289472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$58C938BB-26EB-41E8-B23E-0B3AA91CB0A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f26ad2d83a7da4074bbb2aa071cb6c6aa2918c9f","datavalue":{"value":{"entity-type":"item","numeric-id":4552652,"id":"Q4552652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1399190$9E8B590B-ED4A-4725-BCFE-BA1317D1996E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e69ab893468b67090a9f4e65dadd60673a8b9a4","datavalue":{"value":{"entity-type":"item","numeric-id":703812,"id":"Q703812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b0fc595b6f204756833246a390afd689a156bbd","datavalue":{"value":{"amount":"+0.8865094780921936","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":"Q1399190$D7B7563D-6C05-43D5-BA1B-59EA5102088A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b28b2cdc040e9096ed96fecaa3b9a14ac6489e1","datavalue":{"value":{"entity-type":"item","numeric-id":868743,"id":"Q868743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"42186a9095da907cde59e99026eda51a20b526c5","datavalue":{"value":{"amount":"+0.8356013894081116","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":"Q1399190$BF397164-9D89-4556-B166-CAD3B8A6AEF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"218b3213901d48c1a551093786ac3d9eea5de764","datavalue":{"value":{"entity-type":"item","numeric-id":4601028,"id":"Q4601028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"251d07035e7636145d3f4db05559faac66bde1fd","datavalue":{"value":{"amount":"+0.816927969455719","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":"Q1399190$8CBBAD23-2347-422F-B0B2-A6CF15DBCB75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c0b81345bc12f9b63819c339ce6e9bb9686246ae","datavalue":{"value":{"entity-type":"item","numeric-id":3728219,"id":"Q3728219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3bfab3499cd8d69e22271723acf6720774ee7cae","datavalue":{"value":{"amount":"+0.812558650970459","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":"Q1399190$241DB8FF-09D8-4860-ADE2-91D14C897B62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6bbecb380b464aa4244a54fea6ab3e0158b61015","datavalue":{"value":{"entity-type":"item","numeric-id":5879445,"id":"Q5879445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"199eed9a322d179fbf3811b15119acb6bec2ea1c","datavalue":{"value":{"amount":"+0.8108020424842834","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":"Q1399190$ECC2F276-07E9-4C8A-AA6F-150A820DA2D2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Generic-case complexity, decision problems in group theory, and random walks.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Generic-case_complexity,_decision_problems_in_group_theory,_and_random_walks."}}}}}