{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:55Z","timestamp":1740109375948,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,7,4]],"date-time":"2022-07-04T00:00:00Z","timestamp":1656892800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,7,4]],"date-time":"2022-07-04T00:00:00Z","timestamp":1656892800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["DI 435\/7-1"],"award-info":[{"award-number":["DI 435\/7-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2014\/14\/A\/ST6\/00138"],"award-info":[{"award-number":["2014\/14\/A\/ST6\/00138"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2014\/14\/A\/ST6\/00138"],"award-info":[{"award-number":["2014\/14\/A\/ST6\/00138"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2014\/14\/A\/ST6\/00138"],"award-info":[{"award-number":["2014\/14\/A\/ST6\/00138"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100009534","name":"Universit\u00e4t Stuttgart","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100009534","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2024,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The study of the complexity of the equation satisfiability problem in finite groups had been initiated by Goldmann and Russell in (Inf. Comput. <jats:bold>178<\/jats:bold>(1), 253\u2013262, 2002) where they showed that this problem is in  for nilpotent groups while it is -complete for non-solvable groups. Since then, several results have appeared showing that the problem can be solved in polynomial time in certain solvable groups <jats:italic>G<\/jats:italic> having a nilpotent normal subgroup <jats:italic>H<\/jats:italic> with nilpotent factor <jats:italic>G<\/jats:italic>\/<jats:italic>H<\/jats:italic>. This paper shows that such a normal subgroup must exist in each finite group with equation satisfiability solvable in polynomial time, unless the Exponential Time Hypothesis fails.<\/jats:p>","DOI":"10.1007\/s00224-022-10082-z","type":"journal-article","created":{"date-parts":[[2022,7,4]],"date-time":"2022-07-04T04:02:30Z","timestamp":1656907350000},"page":"740-757","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Equation Satisfiability in Solvable Groups"],"prefix":"10.1007","volume":"68","author":[{"given":"Pawe\u0142","family":"Idziak","sequence":"first","affiliation":[]},{"given":"Piotr","family":"Kawa\u0142ek","sequence":"additional","affiliation":[]},{"given":"Jacek","family":"Krzaczkowski","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7645-5867","authenticated-orcid":false,"given":"Armin","family":"Wei\u00df","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,7,4]]},"reference":[{"key":"10082_CR1","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/BF02547953","volume":"133","author":"R Baer","year":"1957","unstructured":"Baer, R.: Engelsche elemente Noetherscher Gruppen. Math. Ann. 133, 256\u2013270 (1957). https:\/\/doi.org\/10.1007\/BF02547953","journal-title":"Math. Ann."},{"key":"10082_CR2","doi-asserted-by":"publisher","unstructured":"Barrington, D.A.M., McKenzie, P., Moore, C., Tesson, P., Th\u00e9rien, D.: Equation satisfiability and program satisfiability for finite monoids. In: Mathematical Foundations of Computer Science 2000, 25th International Symposium, MFCS 2000, Proceedings, Lecture Notes in Computer Science. https:\/\/doi.org\/10.1007\/3-540-44612-5_13, vol. 1893, pp 172\u2013181. Springer (2000)","DOI":"10.1007\/3-540-44612-5_13"},{"issue":"4","key":"10082_CR3","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1007\/s00012-004-1895-8","volume":"52","author":"S Burris","year":"2005","unstructured":"Burris, S., Lawrence, J.: Results on the equivalence problem for finite groups. Algebra Universalis 52(4), 495\u2013500 (2005). https:\/\/doi.org\/10.1007\/s00012-004-1895-8","journal-title":"Algebra Universalis"},{"key":"10082_CR4","doi-asserted-by":"publisher","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer. https:\/\/doi.org\/10.1007\/978-3-319-21275-3 (2015)","DOI":"10.1007\/978-3-319-21275-3"},{"key":"10082_CR5","doi-asserted-by":"publisher","unstructured":"Diekert, V., Elder, M.: Solutions of twisted word equations, EDT0l languages, and context-free groups. In: ICALP 2017, Proceedings, LIPIcs. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2017.96. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2017\/7397, vol. 80, pp 96:1\u201396:14, Dagstuhl (2017)","DOI":"10.4230\/LIPIcs.ICALP.2017.96"},{"key":"10082_CR6","doi-asserted-by":"publisher","unstructured":"Figelius, M., Ganardi, M., Lohrey, M., Zetzsche, G.: The complexity of knapsack problems in wreath products. In: 47th International colloquium on automata, languages, and programming, ICALP 2020, July 8\u201311, 2020, Saarbr\u00fccken, Germany (Virtual Conference). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.126, pp 126:1\u2013126:18 (2020)","DOI":"10.4230\/LIPIcs.ICALP.2020.126"},{"key":"10082_CR7","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/j.jalgebra.2017.10.002","volume":"495","author":"A F\u00f6ldv\u00e1ri","year":"2018","unstructured":"F\u00f6ldv\u00e1ri, A.: The complexity of the equation solvability problem over nilpotent groups. J. Algebra 495, 289\u2013303 (2018). https:\/\/doi.org\/10.1016\/j.jalgebra.2017.10.002","journal-title":"J. Algebra"},{"issue":"03","key":"10082_CR8","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1142\/S0218196720500137","volume":"30","author":"A F\u00f6ldv\u00e1ri","year":"2020","unstructured":"F\u00f6ldv\u00e1ri, A., Horv\u00e1th, G.: The complexity of the equation solvability and equivalence problems over finite groups. Int. J. Algebra Comput. 30 (03), 607\u2013623 (2020). https:\/\/doi.org\/10.1142\/S0218196720500137","journal-title":"Int. J. Algebra Comput."},{"key":"10082_CR9","doi-asserted-by":"publisher","unstructured":"Garreta, A., Miasnikov, A., Ovchinnikov, D.: Diophantine problems in solvable groups. Bull. Math. Sci. https:\/\/doi.org\/10.1142\/S1664360720500058 (2020)","DOI":"10.1142\/S1664360720500058"},{"issue":"1","key":"10082_CR10","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/S0890-5401(02)93173-1","volume":"178","author":"M Goldmann","year":"2002","unstructured":"Goldmann, M., Russell, A.: The complexity of solving equations over finite groups. Inf. Comput. 178(1), 253\u2013262 (2002). https:\/\/doi.org\/10.1006\/inco.2002.3173","journal-title":"Inf. Comput."},{"issue":"4","key":"10082_CR11","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/s00012-011-0163-y","volume":"66","author":"G Horv\u00e1th","year":"2011","unstructured":"Horv\u00e1th, G.: The complexity of the equivalence and equation solvability problems over nilpotent rings and groups. Algebra Universalis 66(4), 391\u2013403 (2011). https:\/\/doi.org\/10.1007\/s00012-011-0163-y","journal-title":"Algebra Universalis"},{"key":"10082_CR12","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/j.jalgebra.2015.03.015","volume":"433","author":"G Horv\u00e1th","year":"2015","unstructured":"Horv\u00e1th, G.: The complexity of the equivalence and equation solvability problems over meta-Abelian groups. J. Algebra 433, 208\u2013230 (2015). https:\/\/doi.org\/10.1016\/j.jalgebra.2015.03.015","journal-title":"J. Algebra"},{"issue":"5","key":"10082_CR13","doi-asserted-by":"publisher","first-page":"931","DOI":"10.1142\/S0218196706003256","volume":"16","author":"G Horv\u00e1th","year":"2006","unstructured":"Horv\u00e1th, G., Szab\u00f3, C.A.: The complexity of checking identities over finite groups. IJAC 16(5), 931\u2013940 (2006). https:\/\/doi.org\/10.1142\/S0218196706003256","journal-title":"IJAC"},{"issue":"4","key":"10082_CR14","first-page":"23","volume":"13","author":"G Horv\u00e1th","year":"2011","unstructured":"Horv\u00e1th, G., Szab\u00f3, C.: The extended equivalence and equation solvability problems for groups. Discrete. Math. Theor. Comput. Sci. 13(4), 23\u201332 (2011)","journal-title":"Math. Theor. Comput. Sci."},{"issue":"3","key":"10082_CR15","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1112\/blms\/bdm030","volume":"39","author":"G Horv\u00e1th","year":"2007","unstructured":"Horv\u00e1th, G., M\u00e9rai, L., Szab\u00f3, C., Lawrence, J.: The complexity of the equivalence problem for nonsolvable groups. Bull. Lond. Math. Soc. 39(3), 433\u2013438 (2007). https:\/\/doi.org\/10.1112\/blms\/bdm030","journal-title":"Bull. Lond. Math. Soc."},{"key":"10082_CR16","volume-title":"Endliche Gruppen. I. Die Grundlehren der Mathematischen Wissenschaften Band, vol. 134","author":"B Huppert","year":"1967","unstructured":"Huppert, B.: Endliche Gruppen. I. Die Grundlehren der Mathematischen Wissenschaften Band, vol. 134. Springer, Berlin-New York (1967)"},{"key":"10082_CR17","doi-asserted-by":"publisher","unstructured":"Idziak, P.M., Krzaczkowski, J.: Satisfiability in multi-valued circuits. In: Proceedings of the 33rd Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS \u201918. https:\/\/doi.org\/10.1145\/3209108.3209173. Full version in SIAM Journal on Computing, 53(2022), 337\u2013378 https:\/\/doi.org\/10.1137\/18M1220194, pp 550\u2013558. Association for Computing Machinery, New York (2018)","DOI":"10.1145\/3209108.3209173 10.1137\/18M1220194"},{"key":"10082_CR18","doi-asserted-by":"publisher","unstructured":"Idziak, P.M., Kawa\u0142ek, P., Krzaczkowski, J.: Intermediate problems in modular circuits satisfiability. In: Proceedings of the 35th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS \u201920. https:\/\/doi.org\/10.1145\/3373718.3394780, pp 578\u2013590. Association for Computing Machinery, New York (2020)","DOI":"10.1145\/3373718.3394780"},{"key":"10082_CR19","doi-asserted-by":"publisher","unstructured":"Idziak, P.M., Kawalek, P., Krzaczkowski, J.: Complexity of modular circuits. In 37th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS) (LICS \u201922), August 2\u20135, 2022, Haifa, Israel. ACM, New York, NY, USA, 11 pages. https:\/\/doi.org\/10.1145\/3531130.3533350 (2021)","DOI":"10.1145\/3531130.3533350"},{"issue":"4","key":"10082_CR20","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity. J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001). https:\/\/doi.org\/10.1006\/jcss.2001.1774","journal-title":"J. Comput. Syst. Sci."},{"key":"10082_CR21","doi-asserted-by":"publisher","unstructured":"Kawa\u0142ek, P., Krzaczkowski, J.: Even faster algorithms for CSAT over supernilpotent algebras. In: 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), Leibniz International Proceedings in Informatics (LIPIcs). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2020.55, vol. 170, pp 55:1\u201355:13. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2020)","DOI":"10.4230\/LIPIcs.MFCS.2020.55"},{"issue":"1","key":"10082_CR22","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/s10474-019-00924-7","volume":"159","author":"M Kompatscher","year":"2019","unstructured":"Kompatscher, M.: Notes on extended equation solvability and identity checking for groups. Acta Math. Hungar. 159(1), 246\u2013256 (2019). https:\/\/doi.org\/10.1007\/s10474-019-00924-7","journal-title":"Acta Math. Hungar."},{"key":"10082_CR23","doi-asserted-by":"publisher","unstructured":"Lohrey, M., S\u00e9nizergues, G.: Theories of HNN-extensions and amalgamated products. In: ICALP 2006, Proceedings. https:\/\/doi.org\/10.1007\/11787006_43, pp 504\u2013515 (2006)","DOI":"10.1007\/11787006_43"},{"key":"10082_CR24","unstructured":"Lohrey, M., Wei\u00df, A.: The power word problem. In: 44h International symposium on mathematical foundations of computer science, MFCS 2019, proceedings, LIPIcs. http:\/\/www.dagstuhl.de\/dagpub\/978-3-95977-117-7, vol. 138, pp 43:1\u201343:15. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"key":"10082_CR25","first-page":"735","volume":"48","author":"GS Makanin","year":"1984","unstructured":"Makanin, G.S.: Decidability of the universal and positive theories of a free group. Izv. Akad. Nauk SSSR Ser. Mat. 48, 735\u2013749 (1984). In Russian; English translation in: Math. USSR Izvestija, 25, 75\u201388, 1985","journal-title":"Izv. Akad. Nauk SSSR Ser. Mat."},{"key":"10082_CR26","first-page":"354","volume":"11","author":"YV Matijasevic","year":"1970","unstructured":"Matijasevic, Y.V.: Enumerable sets are diophantine. Soviet. Math. Dokl. 11, 354\u2013358 (1970). https:\/\/ci.nii.ac.jp\/naid\/10009422455\/en\/","journal-title":"Math. Dokl."},{"key":"10082_CR27","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison Wesley, Reading (1994)"},{"key":"10082_CR28","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8594-1","volume-title":"A Course in the Theory of Groups Graduate Texts in Mathematics, 2nd edn, vol. 80","author":"DJS Robinson","year":"1996","unstructured":"Robinson, D.J.S.: A Course in the Theory of Groups Graduate Texts in Mathematics, 2nd edn, vol. 80. Springer, New York (1996). https:\/\/doi.org\/10.1007\/978-1-4419-8594-1"},{"key":"10082_CR29","doi-asserted-by":"publisher","unstructured":"Roman\u2019kov, V.: Equations in free metabelian groups. Siberian Math. J. 20. https:\/\/doi.org\/10.1007\/BF00969959 (1979)","DOI":"10.1007\/BF00969959"},{"key":"10082_CR30","doi-asserted-by":"publisher","unstructured":"Wei\u00df, A.: Hardness of equations over finite solvable groups under the exponential time hypothesis. In: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), Leibniz International Proceedings in Informatics (LIPIcs). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.102, vol. 168, pp 102:1\u2013102:19. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2020)","DOI":"10.4230\/LIPIcs.ICALP.2020.102"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-022-10082-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-022-10082-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-022-10082-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,23]],"date-time":"2024-08-23T21:16:54Z","timestamp":1724447814000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-022-10082-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,4]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["10082"],"URL":"https:\/\/doi.org\/10.1007\/s00224-022-10082-z","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2022,7,4]]},"assertion":[{"value":"15 April 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 July 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}