{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T21:28:22Z","timestamp":1768339702771,"version":"3.49.0"},"reference-count":42,"publisher":"World Scientific Pub Co Pte Ltd","issue":"03","funder":[{"name":"DFG","award":["Lo748\/12-1"],"award-info":[{"award-number":["Lo748\/12-1"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2023,5]]},"abstract":"<jats:p> We prove that the power word problem for certain metabelian subgroups of [Formula: see text] (including the solvable Baumslag\u2013Solitar groups [Formula: see text]) belongs to the circuit complexity class [Formula: see text]. In the power word problem, the input consists of group elements [Formula: see text] and binary encoded integers [Formula: see text] and it is asked whether [Formula: see text] holds. Moreover, we prove that the knapsack problem for [Formula: see text] is [Formula: see text]-complete. In the knapsack problem, the input consists of group elements [Formula: see text] and it is asked whether the equation [Formula: see text] has a solution in [Formula: see text]. For the more general case of a system of so-called exponent equations, where the exponent variables [Formula: see text] can occur multiple times, we show that solvability is undecidable for [Formula: see text]. <\/jats:p>","DOI":"10.1142\/s0218196723500285","type":"journal-article","created":{"date-parts":[[2023,3,23]],"date-time":"2023-03-23T15:04:46Z","timestamp":1679583886000},"page":"617-639","source":"Crossref","is-referenced-by-count":4,"title":["Knapsack and the power word problem in solvable Baumslag\u2013Solitar groups"],"prefix":"10.1142","volume":"33","author":[{"given":"Moses","family":"Ganardi","sequence":"first","affiliation":[{"name":"Max Planck Institute for Software Systems (MPI-SWS), Germany"}]},{"given":"Markus","family":"Lohrey","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Siegen, Germany"}]},{"given":"Georg","family":"Zetzsche","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Software Systems (MPI-SWS), Germany"}]}],"member":"219","published-online":{"date-parts":[[2023,4,21]]},"reference":[{"key":"S0218196723500285BIB001","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/978-3-662-44465-8_2","volume-title":"Proc. 39th Int. Symp. Mathematical Foundations of Computer Science 2014, MFCS 2014","volume":"8635","author":"Allender E.","year":"2014"},{"key":"S0218196723500285BIB002","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity \u2014 A Modern Approach","author":"Arora S.","year":"2009"},{"key":"S0218196723500285BIB003","first-page":"498","volume-title":"Proc. Seventh Annual ACM-SIAM Symp. Discrete Algorithms, SODA 1996","author":"Babai L.","year":"1996"},{"issue":"3","key":"S0218196723500285BIB004","volume":"14","author":"Bartholdi L.","year":"2023","journal-title":"ACM Trans. Comput. Theory"},{"issue":"1","key":"S0218196723500285BIB005","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1007\/BF01211007","volume":"75","author":"Baumslag G.","year":"1961","journal-title":"Math. Z."},{"key":"S0218196723500285BIB006","series-title":"Leibniz International Proceedings in Informatics","first-page":"11:1","volume-title":"Proc. 38th Int. Symp. Theoretical Aspects of Computer Science, STACS 2021","volume":"187","author":"Bergstr\u00e4\u00dfer P.","year":"2021"},{"key":"S0218196723500285BIB007","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1007\/3-540-51084-2_22","volume-title":"Proc. 47th Int. Symp. Symbolic and Algebraic Computation, ISSAC 1988","volume":"358","author":"Bradford R. J.","year":"1989"},{"key":"S0218196723500285BIB009","first-page":"191","volume":"1","author":"Bruy\u00e8re V.","year":"1994","journal-title":"Bull. Belgian Math. Soc."},{"issue":"1","key":"S0218196723500285BIB010","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1002\/malq.19600060105","volume":"6","author":"B\u00fcchi J. R.","year":"1960","journal-title":"Math. Logic Quart."},{"issue":"4","key":"S0218196723500285BIB011","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1002\/malq.19880340410","volume":"34","author":"B\u00fcchi J. R.","year":"1988","journal-title":"Math. Log. Quart."},{"issue":"6","key":"S0218196723500285BIB012","doi-asserted-by":"crossref","first-page":"1878","DOI":"10.1137\/S0097539794276853","volume":"29","author":"Cai J.-Y.","year":"2000","journal-title":"SIAM J. Comput."},{"key":"S0218196723500285BIB014","first-page":"43","volume":"18","author":"Dudkin F.","year":"2018","journal-title":"Sib. J. Pure Appl. Math."},{"issue":"5","key":"S0218196723500285BIB015","doi-asserted-by":"crossref","first-page":"955","DOI":"10.1137\/0218066","volume":"18","author":"Eberly W.","year":"1989","journal-title":"SIAM J. Comput."},{"key":"S0218196723500285BIB016","series-title":"Leibniz International Proceedings in Informatics","first-page":"126:1","volume-title":"Proc. 47th Int. Colloquium on Automata, Languages, and Programming, ICALP 2020","volume":"168","author":"Figelius M.","year":"2020"},{"issue":"1","key":"S0218196723500285BIB017","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1016\/j.jalgebra.2021.08.016","volume":"589","author":"Figelius M.","year":"2022","journal-title":"J. Algebra"},{"key":"S0218196723500285BIB018","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/j.jsc.2015.05.006","volume":"74","author":"Frenkel E.","year":"2016","journal-title":"J. Symb. Comput."},{"key":"S0218196723500285BIB019","series-title":"Leibniz International Proceedings in Informatics","first-page":"329","volume-title":"Proc. 32nd Int. Symp. Theoretical Aspects of Computer Science, STACS 2015","volume":"30","author":"Galby E.","year":"2015"},{"key":"S0218196723500285BIB020","series-title":"Leibniz International Proceedings in Informatics","first-page":"32:1","volume-title":"Proc. 35th Symp. Theoretical Aspects of Computer Science, STACS 2018","volume":"96","author":"Ganardi M.","year":"2018"},{"key":"S0218196723500285BIB021","first-page":"422","volume-title":"Proc. 34th Annual Symp. Foundations of Computer Science, FOCS 1993","author":"Ge G.","year":"1993"},{"key":"S0218196723500285BIB022","first-page":"1","volume-title":"Proc. 34th Annual ACM\/IEEE Symp. Logic in Computer Science, LICS 2019","author":"Gu\u00e9pin F.","year":"2019"},{"issue":"4","key":"S0218196723500285BIB023","doi-asserted-by":"crossref","DOI":"10.1142\/S0218196712500312","volume":"22","author":"Guyot L.","year":"2012","journal-title":"Int. J. Algebra Comput."},{"issue":"2","key":"S0218196723500285BIB024","doi-asserted-by":"crossref","first-page":"765","DOI":"10.4171\/GGD\/455","volume":"12","author":"Guyot L.","year":"2018","journal-title":"Groups Geom. Dyn."},{"issue":"4","key":"S0218196723500285BIB026","doi-asserted-by":"crossref","first-page":"695","DOI":"10.1016\/S0022-0000(02)00025-9","volume":"65","author":"Hesse W.","year":"2002","journal-title":"J. Comput. Syst. Sci."},{"issue":"225","key":"S0218196723500285BIB027","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1515\/crll.1967.225.209","volume":"1967","author":"Hooley C.","year":"1967","journal-title":"J. Reine Angew. Math."},{"issue":"5","key":"S0218196723500285BIB028","doi-asserted-by":"crossref","first-page":"1459","DOI":"10.1007\/s00453-017-0343-z","volume":"80","author":"K\u00f6nig D.","year":"2018","journal-title":"Algorithmica"},{"key":"S0218196723500285BIB029","series-title":"Contemporary Mathematics","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1090\/conm\/677\/13625","volume-title":"Algebra and Computer Science","volume":"677","author":"K\u00f6nig D.","year":"2016"},{"key":"S0218196723500285BIB030","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0041-0","volume-title":"Algebra","author":"Lang S.","year":"2002"},{"key":"S0218196723500285BIB031","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/3-540-49381-6_27","volume-title":"Proc. 9th Int. Symp. Algorithms and Computation, ISAAC 1998","volume":"1533","author":"Lange K.-J.","year":"1998"},{"key":"S0218196723500285BIB032","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1515\/9783110285581.267","volume-title":"Number Theory in Progress: Diophantine Problems and Polynomials","volume":"1","author":"Lenstra H. W.","year":"1999"},{"key":"S0218196723500285BIB033","series-title":"Springer Briefs in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4939-0748-9","volume-title":"The Compressed Word Problem for Groups","author":"Lohrey M.","year":"2014"},{"key":"S0218196723500285BIB034","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1016\/j.jalgebra.2019.04.008","volume":"545","author":"Lohrey M.","year":"2020","journal-title":"J. Algebra"},{"key":"S0218196723500285BIB035","series-title":"Leibniz International Proceedings in Informatics","first-page":"43:1","volume-title":"Proc. 44th Int. Symp. Mathematical Foundations of Computer Science, MFCS 2019","volume":"138","author":"Lohrey M.","year":"2019"},{"issue":"1","key":"S0218196723500285BIB036","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1007\/s00224-017-9808-3","volume":"62","author":"Lohrey M.","year":"2018","journal-title":"Theory Comput. Syst."},{"key":"S0218196723500285BIB037","series-title":"Leibniz International Proceedings in Informatics","first-page":"67:1","volume-title":"Proc. 45th Int. Symp. Mathematical Foundations of Computer Science, MFCS 2020","volume":"170","author":"Lohrey M.","year":"2020"},{"issue":"9","key":"S0218196723500285BIB038","doi-asserted-by":"crossref","first-page":"4655","DOI":"10.1090\/S0002-9947-10-04959-7","volume":"362","author":"Miasnikov A.","year":"2010","journal-title":"Trans. Amer. Math. Soc."},{"issue":"1","key":"S0218196723500285BIB039","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1515\/gcc-2017-0006","volume":"9","author":"Mishchenko A.","year":"2017","journal-title":"Groups Complex. Cryptol."},{"key":"S0218196723500285BIB040","doi-asserted-by":"crossref","first-page":"987","DOI":"10.1090\/S0025-5718-2014-02880-9","volume":"84","author":"Myasnikov A.","year":"2015","journal-title":"Math. Comput."},{"key":"S0218196723500285BIB041","volume-title":"Elementary Methods in Number Theory","author":"Nathanson M. B.","year":"2000"},{"key":"S0218196723500285BIB042","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1007\/978-3-031-05578-2_23","volume-title":"Proc. the 26th Int. Conf. Developments in Language Theory, DLT 2022","volume":"13257","author":"Stober F.","year":"2022"},{"key":"S0218196723500285BIB043","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to Circuit Complexity","author":"Vollmer H.","year":"1999"},{"key":"S0218196723500285BIB045","series-title":"Contemporary Mathematics","doi-asserted-by":"crossref","DOI":"10.1090\/conm\/677\/13628","volume-title":"Algebra and Computer Science","volume":"677","author":"Wei\u00df A.","year":"2016"},{"key":"S0218196723500285BIB046","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511470967","volume-title":"Random Walks on Infinite Graphs and Groups","author":"Woess W.","year":"2000"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196723500285","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T08:33:59Z","timestamp":1685090039000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0218196723500285"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,21]]},"references-count":42,"journal-issue":{"issue":"03","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["10.1142\/S0218196723500285"],"URL":"https:\/\/doi.org\/10.1142\/s0218196723500285","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,21]]}}}