Simple view
Full metadata view
Authors
Statistics
Satisfiability of circuits and equations over finite Malcev algebras
circuit satisfiability
solving equations
exponential Time Hypothesis
We show that the satisfiability of circuits over finite Malcev algebra A is NP-complete or A is nilpotent. This strengthens the result from our earlier paper [18] where nilpotency has been enforced, however with the use of a stronger assumption that no homomorphic image of A has NP-complete circuits satisfiability. Our methods are moreover strong enough to extend our result of [14] from groups to Malcev algebras. Namely we show that tractability of checking if an equation over such an algebra A has a solution enforces its nice structure: A must have a nilpotent congruence ν such that also the quotient algebra A{ν is nilpotent. Otherwise, if A has no such congruence ν then the Exponential Time Hypothesis yields a quasipolynomial lower bound. Both our results contain important steps towards a full characterization of finite algebras with tractable circuit satisfiability as well as equation satisfiability.
dc.abstract.en | We show that the satisfiability of circuits over finite Malcev algebra A is NP-complete or A is nilpotent. This strengthens the result from our earlier paper [18] where nilpotency has been enforced, however with the use of a stronger assumption that no homomorphic image of A has NP-complete circuits satisfiability. Our methods are moreover strong enough to extend our result of [14] from groups to Malcev algebras. Namely we show that tractability of checking if an equation over such an algebra A has a solution enforces its nice structure: A must have a nilpotent congruence ν such that also the quotient algebra A{ν is nilpotent. Otherwise, if A has no such congruence ν then the Exponential Time Hypothesis yields a quasipolynomial lower bound. Both our results contain important steps towards a full characterization of finite algebras with tractable circuit satisfiability as well as equation satisfiability. | pl |
dc.affiliation | Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej | pl |
dc.affiliation | Wydział Matematyki i Informatyki | pl |
dc.conference | 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) | |
dc.conference.city | Marsylia | |
dc.conference.country | Francja | |
dc.conference.datefinish | 2022-03-18 | |
dc.conference.datestart | 2022-03-15 | |
dc.conference.shortcut | STACS | |
dc.contributor.author | Idziak, Paweł - 128365 | pl |
dc.contributor.author | Kawałek, Piotr - 216060 | pl |
dc.contributor.author | Krzaczkowski, Jacek - 142023 | pl |
dc.contributor.editor | Berenbrink, Petra | pl |
dc.contributor.editor | Monmege, Benjamin | pl |
dc.date.accessioned | 2022-03-31T12:06:53Z | |
dc.date.available | 2022-03-31T12:06:53Z | |
dc.date.issued | 2022 | pl |
dc.date.openaccess | 0 | |
dc.description.accesstime | w momencie opublikowania | |
dc.description.conftype | international | pl |
dc.description.physical | 37:1-37:14 | pl |
dc.description.series | Leibniz International Proceedings in Informatics | |
dc.description.seriesnumber | Vol. 219 | |
dc.description.version | ostateczna wersja wydawcy | |
dc.description.volume | 219 | pl |
dc.identifier.doi | 10.4230/LIPIcs.STACS.2022.37 | pl |
dc.identifier.isbn | 978-3-95977-222-8 | pl |
dc.identifier.project | 2014/14/A/ST6/00138 | pl |
dc.identifier.seriesissn | 1868-8969 | |
dc.identifier.uri | https://ruj.uj.edu.pl/xmlui/handle/item/289646 | |
dc.language | eng | pl |
dc.language.container | eng | pl |
dc.pubinfo | Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatik | pl |
dc.rights | Udzielam licencji. Uznanie autorstwa 4.0 Międzynarodowa | * |
dc.rights.licence | CC-BY | |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/legalcode.pl | * |
dc.share.type | inne | |
dc.subject.en | circuit satisfiability | pl |
dc.subject.en | solving equations | pl |
dc.subject.en | exponential Time Hypothesis | pl |
dc.subtype | ConferenceProceedings | pl |
dc.title | Satisfiability of circuits and equations over finite Malcev algebras | pl |
dc.title.container | 39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022, March 15-18, 2022, Marseille, France | pl |
dc.type | BookSection | pl |
dspace.entity.type | Publication |
* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.
Views
26
Views per month
Views per city
Downloads
Open Access