{"entities":{"Q1851485":{"pageid":1862227,"ns":120,"title":"Item:Q1851485","lastrevid":73564509,"modified":"2026-04-14T16:28:41Z","type":"item","id":"Q1851485","labels":{"en":{"language":"en","value":"Isoperimetric functions of groups and computational complexity of the word problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1851141"}},"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":"Q1851485$2FC9B266-A82E-44AE-A4EA-065CC01955D3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4d6641b3854254824266dbc95852c5e63ab85b57","datavalue":{"value":{"text":"Isoperimetric functions of groups and computational complexity of the word problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1851485$9DB56808-EE2B-4D91-A8B8-3900107A71CA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"85a86f748a4fa2519abab7b001767ba92d0a1b5f","datavalue":{"value":"1026.20018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1851485$7EC0A975-2A37-4656-86D7-B4C04DCBBB9E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"78727faf4683a3a603e604c1eaac6d4ae92f7a2f","datavalue":{"value":"10.2307/3597196","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1851485$5801D36C-4421-465D-A8C4-C2D192D192FE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1af85c7b2f6fd07526dd5f6ad7e9d1c876779e29","datavalue":{"value":{"entity-type":"item","numeric-id":766115,"id":"Q766115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1851485$426B0D86-FCB0-49C5-9554-0A7093C17918","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b355aee7ddf8eb2827aa952bd026a74b6dfa11c0","datavalue":{"value":{"entity-type":"item","numeric-id":1408937,"id":"Q1408937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1851485$1FE0F80C-79AA-41E5-8CD4-10E27A5A7791","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"862afb06b461dcc1ff46d6df9b011842f09f8803","datavalue":{"value":{"entity-type":"item","numeric-id":1016797,"id":"Q1016797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1851485$03F6E7F3-227C-4CC1-8600-9D73238F6E23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"04b2eec9d6bfe62fe82efa74c284698108cf2d44","datavalue":{"value":{"entity-type":"item","numeric-id":6481255,"id":"Q6481255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1851485$306CD5D3-F159-47E3-BDD7-45EB03A11673","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"553c7ad508f4615999d4ef926cfdf75d436f510c","datavalue":{"value":{"entity-type":"item","numeric-id":175062,"id":"Q175062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1851485$6EEEF951-773D-4713-8243-4561197C3E3E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"eedebd3825925054d465c2c307c8646ae6c8dd0b","datavalue":{"value":{"time":"+2003-10-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1851485$6359B497-914A-4C6E-B52E-5A4B18D8797B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7b3f6429e911106841883e92b83811ecd78e16fe","datavalue":{"value":"https://arxiv.org/abs/math/9811106","type":"string"},"datatype":"url"},"type":"statement","id":"Q1851485$660CCC9A-419D-4C38-BDFE-4D5425193B5A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"12685207ab366c12ea68704f9d0f3de7111acec8","datavalue":{"value":"The paper completes the work started by \\textit{A.~Yu. Ol'shanskij} [Mat. Sb. 188, No. 1, 51-98 (1997; Zbl 0905.20020)] and \\textit{M.~V. Sapir, J.-C. Birget, E.~Rips} [Ann. Math. (2) 156, No. 2, 345-466 (2002; see the review Zbl 1026.20021 below)]. The authors prove Birget's embedding conjecture: a finitely generated group \\(G\\) has the word problem solvable in polynomial time by a nondeterministic Turing machine if and only if \\(G\\) is embeddable into a finitely presented group with polynomial isoperimetric function. The embedding can be chosen so that \\(G\\) has bounded distortion in \\(H\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1851485$F770A61F-8391-48D8-8923-D50452E5A743","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5608e4dbe85e8f6c220cc8afcea2a4ada066e3fa","datavalue":{"value":"20F05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1851485$8F5E2ADA-9FA9-4E76-B4D0-28CCB71A94BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"85721e41fd9cd62748521a1a3e2d4a9ff2acb1e3","datavalue":{"value":"20F06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1851485$A26D9612-A4F2-42A6-A641-E6C33E885E70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8acfec936c9f92116ab04a417b25b0b6b0e8ab90","datavalue":{"value":"20F10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1851485$73626DDC-657C-4ABB-9F33-24988EDC036A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"639e35a4d8066ba3b320b7c5998ad4d73a0cf431","datavalue":{"value":"20F65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1851485$2A2CF9F9-6D0B-4597-B0A5-76964D317B1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1851485$7CF486E0-3786-4291-B3AA-CF5AE7FC644A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1851485$CC7D5A0D-A9F5-470E-9F42-3642C6D684FB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7d691041c8f76ebe1c6aac262b52438752eaecaf","datavalue":{"value":"1851141","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1851485$9EF3C730-75D2-44CE-B085-18D36575B26A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"541e14ca1a9bb27a1cfe827610ca5ddb594a16de","datavalue":{"value":"word problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1851485$4DA75247-669E-4F73-9629-CCEDCDECB835","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ee9121c0801c3856a783c75d0b3df478c6230b4c","datavalue":{"value":"van Kampen diagrams","type":"string"},"datatype":"string"},"type":"statement","id":"Q1851485$C0250922-A76C-4470-99F2-CE9F7667825C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ce94514b8f47d971af3c9a726c7b871020b64705","datavalue":{"value":"isoperimetric functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1851485$7E4857A3-DD0C-44AA-BACA-269DD86E7774","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"15cdc4c1fde41e8a0644d63c4d427b4fcbb62fcc","datavalue":{"value":"Dehn functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1851485$514B0408-3333-4254-97A3-CC3B8B1001C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53064f6609fb5177611c085d6f78e739c7e3f7f6","datavalue":{"value":"time complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1851485$38795B25-0B04-4F50-BD88-17E3793F017E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"db81b778ba41a5d29991e53311f8621b3af1bce4","datavalue":{"value":"\\(S\\)-machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1851485$DFC716A9-A3BE-459C-9CFE-520578C842E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"542470d6f63fefcd2ae937cc78d1c833a1db112c","datavalue":{"value":"finitely generated groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q1851485$EA0DED8E-C790-48BF-A65A-8945886A5FC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1cb45a7fad3616cfdc6377269f8a1b970b78470f","datavalue":{"value":"finitely presented groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q1851485$E66CB51F-F1A8-47CD-AEC4-F10447C6DD30","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":"Q1851485$1343C037-1DE2-4CB1-8906-8C0FAFA935C2","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":"Q1851485$DE7A3928-AA03-4552-B275-3872E6F0CB42","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a609a3206b23fa15b61fe1d8edc6f78978439d90","datavalue":{"value":"W2026119659","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1851485$B1C0FCB5-F7BF-4214-9337-A36534078055","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"38a19f65836768c647bea6c4e57efed848377a80","datavalue":{"value":"Q56388581","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1851485$B4004FD1-BD72-4DBC-B59A-A7775B91C5DB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c13065db76efb81bd5c221934f416f1c439bd1cd","datavalue":{"value":{"entity-type":"item","numeric-id":2841376,"id":"Q2841376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"011383a00ff3fef279218cbfec2db17eefce38c9","datavalue":{"value":{"amount":"+0.8658792972564697","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":"Q1851485$1159A2E3-5F51-43FE-9587-AD5F3C32ABE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e7fefb8e406064676af0b6c975a7288164e4b0b","datavalue":{"value":{"entity-type":"item","numeric-id":1851484,"id":"Q1851484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"25d061ac61b1d3dad7fab11f06172aef22126e35","datavalue":{"value":{"amount":"+0.8458274602890015","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":"Q1851485$ED2298C6-19F1-413D-872F-D6D4075910AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"564a297ccbd89ef2ad93ad01d1667eea0e8583fa","datavalue":{"value":{"entity-type":"item","numeric-id":3448552,"id":"Q3448552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c01a51b58bbe0a030b9e6e9e744151f90fed539c","datavalue":{"value":{"amount":"+0.8440943956375122","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":"Q1851485$B16AFB00-33FE-4054-A3C0-E0508A1D1DC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ce9c46692c4e596428e8551d663737cab5a59c9","datavalue":{"value":{"entity-type":"item","numeric-id":395608,"id":"Q395608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84455cf1c9f266383f59acedcf12764bcf51b9d2","datavalue":{"value":{"amount":"+0.8275591135025024","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":"Q1851485$0D53B021-4168-4181-8081-159421B5EAFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d1ddc3450e1a47db7ea11d53c1acfbb6eebbe3c","datavalue":{"value":{"entity-type":"item","numeric-id":4354236,"id":"Q4354236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"594de5d976a84f8964a5df46ae7fbdddb38e4fff","datavalue":{"value":{"amount":"+0.8252968192100525","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":"Q1851485$803636D4-F47F-4883-A811-86E3699ED421","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Isoperimetric functions of groups and computational complexity of the word problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Isoperimetric_functions_of_groups_and_computational_complexity_of_the_word_problem"}}}}}