Solvable group isomorphism is (almost) in NP coNP

DOI10.1145/1944857.1944859zbMATH Open1322.68092OpenAlexW2156088544MaRDI QIDQ2947552FDOQ2947552

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

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

zbMATH Keywords

limited nondeterminismderandomizationcomputational and structural complexityArthur-Merlin games

Mathematics Subject Classification ID

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

Cited In (6)

• Breaking the \(n^{\log^n}\) barrier for solvable-group isomorphism
• Enumerating abelian \(p\)-groups
• Solvable black-box group problems are low for PP
• Algorithms for group isomorphism via group extensions and cohomology
• Nearly linear time isomorphism algorithms for some nonabelian group classes
• Linear space data structures for finite groups with constant query-time

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)