Solvable Group Isomorphism Is (Almost) in NP ∩ coNP

DOI10.1145/1944857.1944859zbMath1322.68092MaRDI 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

derandomization; limited nondeterminism; computational and structural complexity; Arthur-Merlin games

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

91A05: 2-person games

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)

68W20: Randomized algorithms