Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. The extended equival ...
Article

The extended equivalence and equation solvability problems for groups

Gabor Horvath (1), Csaba Szabo (2)
(1) Institute of Mathematics [Debrecen]
(2) Department of Algebra and Number Theory [Budapest]
Download article
Open on HAL
Imported on
September 29, 2010
Published on
November 15, 2011
Last modified on
March 31, 2025
Volume 13
vol. 13:4, Special Issue in honor of Laci Babai's 60th birthday: Combinatorics, Groups, Algorithms, and Complexity
DOI
10.46298/dmtcs.536
License
https://about.hal.science/hal-authorisation-v1
Indicators
656
Views
646
Downloads

The extended equivalence and equation solvability problems for groups

Gabor Horvath (1), Csaba Szabo (2)
(1) Institute of Mathematics [Debrecen]
(2) Department of Algebra and Number Theory [Budapest]
Abstract
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.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Cited by

Source: OpenCitations

  • The Complexity of Checking Quasi-Identities over Finite Algebras with a Mal'cev Term

    DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)

    Authors : Aichinger, Grünbacher

    Journal reference : Volume , 2023, pp.

    DOI : 10.4230/lipics.stacs.2023.4

  • On NP-Complete Search Problems on Finite Algebras

    2024 IEEE 54th International Symposium on Multiple-Valued Logic (ISMVL)

    Authors : Bernardo Rossi ORCID, Erhard Aichinger ORCID

    Journal reference : Volume 125, 2024, pp. 131-136

    DOI : 10.1109/ismvl60454.2024.00034

  • Satisfiability in multi-valued circuits

    Jagiellonian University Repository (Jagiellonian University)

    Authors : Paweł M. Idziak, Jacek Krzaczkowski ORCID

    Journal reference : Volume , 2018, pp. 550-558

    DOI : 10.1145/3209108.3209173
Preview
Loading PDF preview...