{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T14:15:24Z","timestamp":1753884924794,"version":"3.41.2"},"reference-count":42,"publisher":"World Scientific Pub Co Pte Ltd","issue":"03","funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["622397"],"award-info":[{"award-number":["622397"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Research Council","award":["681988"],"award-info":[{"award-number":["681988"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Math. Log."],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:p> We study the computational complexity of deciding whether a given set of term equalities and inequalities has a solution in an [Formula: see text]-categorical algebra [Formula: see text]. There are [Formula: see text]-categorical groups where this problem is undecidable. We show that if [Formula: see text] is an [Formula: see text]-categorical semilattice or an abelian group, then the problem is in P or NP-hard. The hard cases are precisely those where [Formula: see text] has a uniformly continuous minor-preserving map to the clone of projections on a two-element set. The results provide information about algebras [Formula: see text] such that [Formula: see text] does not satisfy this condition, and they are of independent interest in universal algebra. In our proofs we rely on the Barto\u2013Pinsker theorem about the existence of pseudo-Siggers polymorphisms. To the best of our knowledge, this is the first time that the pseudo-Siggers identity has been used to prove a complexity dichotomy. <\/jats:p>","DOI":"10.1142\/s0219061321500203","type":"journal-article","created":{"date-parts":[[2020,11,8]],"date-time":"2020-11-08T16:08:24Z","timestamp":1604851704000},"source":"Crossref","is-referenced-by-count":1,"title":["Solving equation systems in \u03c9-categorical algebras"],"prefix":"10.1142","volume":"21","author":[{"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Algebra, TU Dresden, 01062 Dresden, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Quinn-Gregson","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Algebra, TU Dresden, 01062 Dresden, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2021,1,6]]},"reference":[{"issue":"1","key":"S0219061321500203BIB003","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2168\/LMCS-8(1:7)2012","volume":"8","author":"Barto L.","year":"2012","journal-title":"Logical Methods Comput. Sci."},{"key":"S0219061321500203BIB004","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-017-1621-9"},{"key":"S0219061321500203BIB006","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4843(70)90006-9"},{"key":"S0219061321500203BIB007","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-3(1:2)2007"},{"key":"S0219061321500203BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.050"},{"key":"S0219061321500203BIB010","doi-asserted-by":"publisher","DOI":"10.1613\/jair.3747"},{"key":"S0219061321500203BIB011","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2010.13"},{"issue":"2","key":"S0219061321500203BIB012","first-page":"1","volume":"8","author":"Bodirsky M.","year":"2012","journal-title":"Logical Methods Comput. Sci. (LMCS)"},{"key":"S0219061321500203BIB013","series-title":"Volume 7 of Dagstuhl Follow-Ups","first-page":"79","volume-title":"The Constraint Satisfaction Problem: Complexity and Approximability","author":"Bodirsky M.","year":"2017"},{"key":"S0219061321500203BIB014","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exi083"},{"key":"S0219061321500203BIB015","doi-asserted-by":"publisher","DOI":"10.1145\/3373718.3394750"},{"key":"S0219061321500203BIB016","first-page":"489","volume-title":"AMS Contemporary Mathematics","volume":"558","author":"Bodirsky M.","year":"2011"},{"key":"S0219061321500203BIB017","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-014-1042-y"},{"key":"S0219061321500203BIB018","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2014-05975-8"},{"key":"S0219061321500203BIB020","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00224-2"},{"first-page":"319","volume-title":"58th IEEE Annual Symp. Foundations of Computer Science, FOCS 2017","author":"Bulatov A. A.","key":"S0219061321500203BIB021"},{"key":"S0219061321500203BIB022","doi-asserted-by":"publisher","DOI":"10.1137\/050628957"},{"key":"S0219061321500203BIB023","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"S0219061321500203BIB024","doi-asserted-by":"publisher","DOI":"10.1090\/tran\/7513"},{"issue":"2","key":"S0219061321500203BIB025","first-page":"220","volume":"7","author":"Dean R. A.","year":"1956","journal-title":"Proc. Am. Math. Soc."},{"key":"S0219061321500203BIB026","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"S0219061321500203BIB027","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(02)93173-1"},{"key":"S0219061321500203BIB028","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511551574"},{"volume-title":"A Shorter Model Theory","year":"1997","author":"Hodges W.","key":"S0219061321500203BIB029"},{"volume-title":"Infinite Abelian Groups","year":"1969","author":"Kaplansky I.","key":"S0219061321500203BIB030"},{"key":"S0219061321500203BIB031","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-005-1279-2"},{"key":"S0219061321500203BIB032","series-title":"Dagstuhl Follow-Ups","volume-title":"The Constraint Satisfaction Problem: Complexity and Approximability","volume":"7","author":"Krokhin A. A.","year":"2017"},{"key":"S0219061321500203BIB033","doi-asserted-by":"publisher","DOI":"10.1145\/321864.321877"},{"key":"S0219061321500203BIB034","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1937-1501929-X"},{"key":"S0219061321500203BIB035","doi-asserted-by":"publisher","DOI":"10.1023\/A:1006365012997"},{"volume-title":"Hilbert\u2019s Tenth Problem","year":"1993","author":"Matiyasevich Y. V.","key":"S0219061321500203BIB036"},{"key":"S0219061321500203BIB037","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44683-4_47"},{"key":"S0219061321500203BIB038","doi-asserted-by":"publisher","DOI":"10.1145\/322186.322198"},{"key":"S0219061321500203BIB039","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(73)90092-6"},{"key":"S0219061321500203BIB040","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(82)90218-6"},{"key":"S0219061321500203BIB041","first-page":"591","volume":"39","author":"Saracino D.","year":"1973","journal-title":"Proc. AMS"},{"volume-title":"Group Theory","year":"1975","author":"Schenkman E.","key":"S0219061321500203BIB042"},{"volume-title":"Theory of Linear and Integer Programming","year":"1998","author":"Schrijver A.","key":"S0219061321500203BIB043"},{"key":"S0219061321500203BIB044","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-010-0082-3"},{"key":"S0219061321500203BIB045","doi-asserted-by":"publisher","DOI":"10.1007\/BF02773695"},{"key":"S0219061321500203BIB046","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139015417"},{"key":"S0219061321500203BIB047","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.38"}],"container-title":["Journal of Mathematical Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219061321500203","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,25]],"date-time":"2021-10-25T12:45:48Z","timestamp":1635165948000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0219061321500203"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,6]]},"references-count":42,"journal-issue":{"issue":"03","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["10.1142\/S0219061321500203"],"URL":"https:\/\/doi.org\/10.1142\/s0219061321500203","relation":{},"ISSN":["0219-0613","1793-6691"],"issn-type":[{"type":"print","value":"0219-0613"},{"type":"electronic","value":"1793-6691"}],"subject":[],"published":{"date-parts":[[2021,1,6]]},"article-number":"2150020"}}