The equation solvability problem over supernilpotent algebras with Mal'cev term
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10383441" target="_blank" >RIV/00216208:11320/18:10383441 - isvavai.cz</a>
Výsledek na webu
<a href="https://doi.org/10.1142/S0218196718500443" target="_blank" >https://doi.org/10.1142/S0218196718500443</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1142/S0218196718500443" target="_blank" >10.1142/S0218196718500443</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
The equation solvability problem over supernilpotent algebras with Mal'cev term
Popis výsledku v původním jazyce
In 2011, Horvath gave a new proof that the equation solvability problem over finite nilpotent groups and rings is in P. In the same paper, he asked whether his proof can be lifted to nilpotent algebras in general. We show that this is in fact possible for supernilpotent algebras with a Mal'cev term. However, we also describe a class of nilpotent, but not supernilpotent algebras with Mal'cev term that have co-NP-complete identity checking problems and NP-complete equation solvability problems. This proves that the answer to Horvath's question is negative in general (assuming P not equal NP).
Název v anglickém jazyce
The equation solvability problem over supernilpotent algebras with Mal'cev term
Popis výsledku anglicky
In 2011, Horvath gave a new proof that the equation solvability problem over finite nilpotent groups and rings is in P. In the same paper, he asked whether his proof can be lifted to nilpotent algebras in general. We show that this is in fact possible for supernilpotent algebras with a Mal'cev term. However, we also describe a class of nilpotent, but not supernilpotent algebras with Mal'cev term that have co-NP-complete identity checking problems and NP-complete equation solvability problems. This proves that the answer to Horvath's question is negative in general (assuming P not equal NP).
Klasifikace
Druh
J<sub>imp</sub> - Článek v periodiku v databázi Web of Science
CEP obor
—
OECD FORD obor
10101 - Pure mathematics
Návaznosti výsledku
Projekt
—
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2018
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
International Journal of Algebra and Computation
ISSN
0218-1967
e-ISSN
—
Svazek periodika
28
Číslo periodika v rámci svazku
6
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
11
Strana od-do
1005-1015
Kód UT WoS článku
000444833400004
EID výsledku v databázi Scopus
2-s2.0-85049349621