Solving promise equations over monoids and groups
We give a complete complexity classification for the problem of finding a solution to a given system of equations over a fixed finite monoid, given that a solution over a more restricted monoid exists. As a corollary, we obtain a complexity classification for the same problem over groups.
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2024
|
| _version_ | 1826313508603559936 |
|---|---|
| author | Larrauri, A Živný, S |
| author_facet | Larrauri, A Živný, S |
| author_sort | Larrauri, A |
| collection | OXFORD |
| description | We give a complete complexity classification for the problem of finding a solution to a given system of equations over a fixed finite monoid, given that a solution over a more restricted monoid exists. As a corollary, we obtain a complexity classification for the same problem over groups. |
| first_indexed | 2024-09-25T04:14:44Z |
| format | Conference item |
| id | oxford-uuid:f6c4d696-8062-4a58-918e-f4885b8c6abd |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-09-25T04:14:44Z |
| publishDate | 2024 |
| publisher | Schloss Dagstuhl – Leibniz-Zentrum für Informatik |
| record_format | dspace |
| spelling | oxford-uuid:f6c4d696-8062-4a58-918e-f4885b8c6abd2024-07-15T11:20:50ZSolving promise equations over monoids and groupsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:f6c4d696-8062-4a58-918e-f4885b8c6abdEnglishSymplectic ElementsSchloss Dagstuhl – Leibniz-Zentrum für Informatik2024Larrauri, AŽivný, SWe give a complete complexity classification for the problem of finding a solution to a given system of equations over a fixed finite monoid, given that a solution over a more restricted monoid exists. As a corollary, we obtain a complexity classification for the same problem over groups. |
| spellingShingle | Larrauri, A Živný, S Solving promise equations over monoids and groups |
| title | Solving promise equations over monoids and groups |
| title_full | Solving promise equations over monoids and groups |
| title_fullStr | Solving promise equations over monoids and groups |
| title_full_unstemmed | Solving promise equations over monoids and groups |
| title_short | Solving promise equations over monoids and groups |
| title_sort | solving promise equations over monoids and groups |
| work_keys_str_mv | AT larrauria solvingpromiseequationsovermonoidsandgroups AT zivnys solvingpromiseequationsovermonoidsandgroups |