Satisfiability of circuits and equations over finite Malcev algebras

2022
book section
conference proceedings
3
dc.abstract.enWe 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.affiliationWydział Matematyki i Informatyki : Instytut Informatyki Analitycznejpl
dc.affiliationWydział Matematyki i Informatykipl
dc.conference39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
dc.conference.cityMarsylia
dc.conference.countryFrancja
dc.conference.datefinish2022-03-18
dc.conference.datestart2022-03-15
dc.conference.shortcutSTACS
dc.contributor.authorIdziak, Paweł - 128365 pl
dc.contributor.authorKawałek, Piotr - 216060 pl
dc.contributor.authorKrzaczkowski, Jacek - 142023 pl
dc.contributor.editorBerenbrink, Petrapl
dc.contributor.editorMonmege, Benjaminpl
dc.date.accessioned2022-03-31T12:06:53Z
dc.date.available2022-03-31T12:06:53Z
dc.date.issued2022pl
dc.date.openaccess0
dc.description.accesstimew momencie opublikowania
dc.description.conftypeinternationalpl
dc.description.physical37:1-37:14pl
dc.description.seriesLeibniz International Proceedings in Informatics
dc.description.seriesnumberVol. 219
dc.description.versionostateczna wersja wydawcy
dc.description.volume219pl
dc.identifier.doi10.4230/LIPIcs.STACS.2022.37pl
dc.identifier.isbn978-3-95977-222-8pl
dc.identifier.project2014/14/A/ST6/00138pl
dc.identifier.seriesissn1868-8969
dc.identifier.urihttps://ruj.uj.edu.pl/xmlui/handle/item/289646
dc.languageengpl
dc.language.containerengpl
dc.pubinfoDagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatikpl
dc.rightsUdzielam licencji. Uznanie autorstwa 4.0 Międzynarodowa*
dc.rights.licenceCC-BY
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/legalcode.pl*
dc.share.typeinne
dc.subject.encircuit satisfiabilitypl
dc.subject.ensolving equationspl
dc.subject.enexponential Time Hypothesispl
dc.subtypeConferenceProceedingspl
dc.titleSatisfiability of circuits and equations over finite Malcev algebraspl
dc.title.container39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022, March 15-18, 2022, Marseille, Francepl
dc.typeBookSectionpl
dspace.entity.typePublication
dc.abstract.enpl
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.affiliationpl
Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej
dc.affiliationpl
Wydział Matematyki i Informatyki
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.authorpl
Idziak, Paweł - 128365
dc.contributor.authorpl
Kawałek, Piotr - 216060
dc.contributor.authorpl
Krzaczkowski, Jacek - 142023
dc.contributor.editorpl
Berenbrink, Petra
dc.contributor.editorpl
Monmege, Benjamin
dc.date.accessioned
2022-03-31T12:06:53Z
dc.date.available
2022-03-31T12:06:53Z
dc.date.issuedpl
2022
dc.date.openaccess
0
dc.description.accesstime
w momencie opublikowania
dc.description.conftypepl
international
dc.description.physicalpl
37:1-37:14
dc.description.series
Leibniz International Proceedings in Informatics
dc.description.seriesnumber
Vol. 219
dc.description.version
ostateczna wersja wydawcy
dc.description.volumepl
219
dc.identifier.doipl
10.4230/LIPIcs.STACS.2022.37
dc.identifier.isbnpl
978-3-95977-222-8
dc.identifier.projectpl
2014/14/A/ST6/00138
dc.identifier.seriesissn
1868-8969
dc.identifier.uri
https://ruj.uj.edu.pl/xmlui/handle/item/289646
dc.languagepl
eng
dc.language.containerpl
eng
dc.pubinfopl
Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatik
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.enpl
circuit satisfiability
dc.subject.enpl
solving equations
dc.subject.enpl
exponential Time Hypothesis
dc.subtypepl
ConferenceProceedings
dc.titlepl
Satisfiability of circuits and equations over finite Malcev algebras
dc.title.containerpl
39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022, March 15-18, 2022, Marseille, France
dc.typepl
BookSection
dspace.entity.type
Publication
Affiliations

* 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
Krakow
9
Prague
3
Dublin
2
Wroclaw
2
Chicago
1
Liberec
1
Oxford
1
Zhengzhou
1
Downloads
idziak_kawalek_satisfiability_of_circuits_and_equations_2021.pdf
52
idziak_kawalek_satisfiability_of_circuits_and_equations_2021.odt
6