Solvable Group Isomorphism Is (Almost) in NP ∩ coNP

DOI10.1145/1944857.1944859zbMath1322.68092OpenAlexW2156088544MaRDI QIDQ2947552

V. Arvind, Jacobo Toran

Publication date: 24 September 2015

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1944857.1944859

zbMATH Keywords

derandomizationlimited nondeterminismcomputational and structural complexityArthur-Merlin games

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Randomized algorithms (68W20)

Related Items (3)

Algorithms for Group Isomorphism via Group Extensions and Cohomology ⋮ Enumerating abelian \(p\)-groups ⋮ Nearly linear time isomorphism algorithms for some nonabelian group classes

This page was built for publication: Solvable Group Isomorphism Is (Almost) in NP ∩ coNP