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

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)

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

(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)