Gabor Horvath ; Csaba Szabo - The extended equivalence and equation solvability problems for groups

dmtcs:536 - Discrete Mathematics & Theoretical Computer Science, November 16, 2011, vol. 13:4, Special Issue in honor of Laci Babai's 60th birthday: Combinatorics, Groups, Algorithms, and Complexity - https://doi.org/10.46298/dmtcs.536
The extended equivalence and equation solvability problems for groupsArticle

Authors: Gabor Horvath 1; Csaba Szabo 2

  • 1 Institute of Mathematics [Debrecen]
  • 2 Department of Algebra and Number Theory [Budapest]

special issue in honor of Laci Babai's 60th birthday: Combinatorics, Groups, Algorithms, and Complexity

[en]
We prove that the extended equivalence problem is solvable in polynomial time for finite nilpotent groups, and coNP-complete, otherwise. We prove that the extended equation solvability problem is solvable in polynomial time for finite nilpotent groups, and NP-complete, otherwise.

https://doi.org/10.46298/dmtcs.536
Source: HAL:hal-00990480v1
Volume: vol. 13:4, Special Issue in honor of Laci Babai's 60th birthday: Combinatorics, Groups, Algorithms, and Complexity
Published on: November 16, 2011
Imported on: September 30, 2010
Keywords: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Licence: Hal authorisation v1

3 Documents citing this article

Share and export

Consultation statistics

This page has been seen 607 times.
This article's PDF has been downloaded 541 times.