{"entities":{"Q6495843":{"pageid":14074616,"ns":120,"title":"Item:Q6495843","lastrevid":55646521,"modified":"2026-02-17T20:18:41Z","type":"item","id":"Q6495843","labels":{"en":{"language":"en","value":"The compressed conjugacy problem in relatively hyperbolic groups"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7841521"}},"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":"Q6495843$6D52B383-D7EE-4D08-871F-F3D4B7DCEE7A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1fdef302c1f50926ef03982a4e98e73886e2e09e","datavalue":{"value":{"text":"The compressed conjugacy problem in relatively hyperbolic groups","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6495843$84EB2AD4-99B3-4FE2-AF61-E0840094D4E1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4379837ed1398a617242a1336a8f80b2ef7c97a7","datavalue":{"value":{"entity-type":"item","numeric-id":169336,"id":"Q169336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6495843$6095B59A-E7A5-43B6-B564-A0DF12400267","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e2a59ee3d603a5b1e501e33362d378b8f1c78ba1","datavalue":{"value":{"entity-type":"item","numeric-id":273098,"id":"Q273098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6495843$4EA89F9D-06AA-4325-A0CE-6E50668F56A5","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":"Q6495843$6DDF5FBC-ABE2-4FAE-9EAB-FEE7F6C48E04","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"98b353a958cc9248956b7b038e8ac0f5d18e0298","datavalue":{"value":{"time":"+2024-05-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6495843$5FB3C43E-D53C-4E76-B62F-97E315BC9939","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c6f319736059ac2d6edf9b5b247167ed033b3868","datavalue":{"value":"The conjugacy problem \\(\\mathsf{CP}(G)\\) for a group \\(G\\) takes as input two words \\(u\\), \\(v\\) over a generating set \\(\\Sigma\\). The problem is solvable if there is an algorithm that can determine for any such input whether \\(u\\) and \\(v\\) are conjugate in \\(G\\). The answer yes or no is returned.NEWLINENEWLINEThe compressed conjugacy problem \\(\\mathsf{CCP}(G)\\) takes as input straight line programs, \\(\\mathcal{G}_{1}\\) and \\(\\mathcal{G}_{2}\\), which define compressed versions of words \\(u\\) and \\(v\\), and asks whether the group elements represented by those values are conjugate in \\(G\\). In the case when the answer is positive, a solution to the problem would normally be expected to compute a conjugator \\(g\\), which would be returned as an straight line program for a word representing \\(g\\). Complexity is measured in terms of the sizes of the input straight line programs, which can be significantly less than the sizes of their values.NEWLINENEWLINEThe main result of the paper under review is Theorem A: The compressed conjugacy problem for a group that is hyperbolic relative to a collection of free abelian subgroups is solvable in polynomial time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6495843$66766893-006D-435D-A302-57E20393D3F5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5bfd82087b720927b1a296c318191d7cfc2aac2e","datavalue":{"value":{"entity-type":"item","numeric-id":284097,"id":"Q284097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6495843$7A7E542F-9079-454C-8454-7E285F75A719","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d746b8d92c753ec921d8d5d21d7a353ee19cc6b6","datavalue":{"value":"20F67","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6495843$44C83C10-785C-47CB-8D22-F307625A7A49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8acfec936c9f92116ab04a417b25b0b6b0e8ab90","datavalue":{"value":"20F10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6495843$DE0A1A92-9C3E-4C96-9524-040DEBCA59CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0da8a0ae39ec16bf06e86cd23430c4f0aa6576dd","datavalue":{"value":"20-08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6495843$FB1C231A-3FE7-45D2-8F17-CD6CF35A7054","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"83d6918a88de0f831e9bf5b45dd1d3156f02b899","datavalue":{"value":"7841521","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6495843$DC04EBBC-A162-4971-BBDF-600CF7D7DBE1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc37741b806fa919248ea28ba240676820498454","datavalue":{"value":"relatively hyperbolic group","type":"string"},"datatype":"string"},"type":"statement","id":"Q6495843$F86C73E0-1EE2-43B7-9B3B-70200DC5255B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3a63ee56c4d2f81c4a9b7f5e8124d077a3591e1b","datavalue":{"value":"conjugacy problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q6495843$E7376CCC-4F36-4FE4-99A4-FBD6BAF5BCD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84d8e21e7a979a5040eb02d3c83f442c01908732","datavalue":{"value":"compressed decision problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q6495843$CD39CEF9-E04E-4F86-9D16-24A25CAFE9D8","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":"Q6495843$86314160-85A3-4D19-951A-F69D526FD431","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c4c4d783910ba9e5f272fd6d7c545eb6037e981","datavalue":{"value":{"entity-type":"item","numeric-id":2821679,"id":"Q2821679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6495843$5ADD375A-4F7C-46BA-8B9A-1861828B2C19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"41419b29f7c05ca995e5582bc31f87e815059e9f","datavalue":{"value":{"entity-type":"item","numeric-id":2888833,"id":"Q2888833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6495843$7C4CF6EC-3582-4F6A-B194-1CDB24548BD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8f5d0749e63668e74a75eb5adf28f40df8e18fd","datavalue":{"value":{"entity-type":"item","numeric-id":4720067,"id":"Q4720067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6495843$C99806EE-F213-43DD-98FB-363B984AEA46","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":"Q6495843$987A15F3-5CED-4674-BF77-452599FAF4CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3900526b18f12d2dad56b87c420a80226a3b7f4e","datavalue":{"value":{"entity-type":"item","numeric-id":5483462,"id":"Q5483462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6495843$B2425419-5E14-4E7E-88E3-726FCA532890","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c74fa60101ba54624433bb93d96d58920da7a19","datavalue":{"value":{"entity-type":"item","numeric-id":5906296,"id":"Q5906296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6495843$8E178839-2FFB-40F8-9542-79DD2133AE2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c8a8e2cecc56297517bbe68a35993768ee7dd47","datavalue":{"value":{"entity-type":"item","numeric-id":2153344,"id":"Q2153344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6495843$2C1D0FB7-DB2C-4BCF-8B43-05E83D47D5D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a243e6fa4e2e08428e45401949d6de9a4b748bc4","datavalue":{"value":{"entity-type":"item","numeric-id":3377332,"id":"Q3377332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6495843$444A3943-8D0D-4052-959E-CBF1220032C7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"329b17b718637d1fccbb56ed15d6cc602ea0c8de","datavalue":{"value":"10.1016/J.JALGEBRA.2024.03.009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6495843$E24550C0-A5EC-4C25-A750-40A97832F61D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"160db68b9580950da2ceeee961250d464bc337f3","datavalue":{"value":{"entity-type":"item","numeric-id":2153344,"id":"Q2153344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02be8a3e6f4c55204622586a4442fa4a144c9c7a","datavalue":{"value":{"amount":"+0.8964875936508179","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":"Q6495843$16540747-5235-4B55-8177-B6B506FCD2DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2a195708ca19bb3bade6ddd58bced14bdcd55dc","datavalue":{"value":{"entity-type":"item","numeric-id":6619327,"id":"Q6619327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06c62f03fed3dbe93a83b3e7b1b353c1bdd2865c","datavalue":{"value":{"amount":"+0.8672348856925964","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":"Q6495843$88E57F07-9D48-4F4B-ABC1-CC1F29AA19EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4dedb1d66336500bf30f1f9f08c0a760eff93642","datavalue":{"value":{"entity-type":"item","numeric-id":5090487,"id":"Q5090487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54303fef0fcc6f8360886a299f9627db2552721c","datavalue":{"value":{"amount":"+0.8546857833862305","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":"Q6495843$2860B208-F6C8-45BA-9E7C-F3276869974B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fcc3f2026566e6880935ca4aa3577adfbedda13c","datavalue":{"value":{"entity-type":"item","numeric-id":2942798,"id":"Q2942798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e716ed3e097ab989f69681fbf5c3da56e0de14c5","datavalue":{"value":{"amount":"+0.8445450663566589","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":"Q6495843$72088FE5-5B80-4F11-B24F-EB6948CB7CDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1622f8657a8935f37ff21d1dcd4c8a4ee467890","datavalue":{"value":{"entity-type":"item","numeric-id":1766289,"id":"Q1766289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd511b247fb78fe71133d927bba66282bc99c41d","datavalue":{"value":{"amount":"+0.8319861888885498","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":"Q6495843$E407591E-3F7D-468F-8290-C6DB60E6A4DB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6495843","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6495843"}}}}}