Solvable group isomorphism is (almost) in NP coNP

DOI10.1145/1944857.1944859MaRDI QIDQ2947552zbMATH OpenOpenAlexFDO

Authors Vikraman Arvind, Jacobo Torán

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

Arthur-Merlin gamescomputational and structural complexityderandomizationlimited nondeterminism

Mathematics Subject Classification ID

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

Recommendations

• Breaking the \(n^{\log^n}\) barrier for solvable-group isomorphism
• Beating the generator-enumeration bound for solvable-group isomorphism
• Bounded Round Interactive Proofs in Finite Groups
• Polynomial-time isomorphism test for groups with abelian Sylow towers.
• New Computational Paradigms

Cited in

(8)

• Solvable black-box group problems are low for PP
• Enumerating abelian \(p\)-groups
• Bounded Round Interactive Proofs in Finite Groups
• Algorithms for group isomorphism via group extensions and cohomology
• Breaking the \(n^{\log^n}\) barrier for solvable-group isomorphism
• Nearly linear time isomorphism algorithms for some nonabelian group classes
• Linear space data structures for finite groups with constant query-time
• On the complexity of problems on graphs defined on groups

This page was built for publication: Solvable group isomorphism is (almost) in \(\mathsf{NP} \cap \mathsf{coNP}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947552)