Solvable black-box group problems are low for PP
From MaRDI portal
Recommendations
- Solvable black-box group problems are low for \(\mathrm{PP}\)
- scientific article; zbMATH DE number 1104166
- Counting Complexity of Solvable Black-Box Group Problems
- Sufficient Conditions for Intractability over Black-Box Groups: Generic Lower Bounds for Generalized DL and DH Problems
- SZK proofs for black-box group problems
- SZK Proofs for Black-Box Group Problems
- scientific article; zbMATH DE number 1284153
- Solvable group isomorphism is (almost) in \(\mathsf{NP} \cap \mathsf{coNP}\)
- Quite free complicated abelian groups, pcf and black boxes
- Breaking the \(n^{\log^n}\) barrier for solvable-group isomorphism
Cites work
- scientific article; zbMATH DE number 3137403 (Why is no real title available?)
- scientific article; zbMATH DE number 1256646 (Why is no real title available?)
- scientific article; zbMATH DE number 475356 (Why is no real title available?)
- scientific article; zbMATH DE number 3109449 (Why is no real title available?)
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Bounded Round Interactive Proofs in Finite Groups
- Does co-NP have short interactive proofs ?
- Fast Monte Carlo algorithms for permutation groups
- Graph isomorphism is in the low hierarchy
- Graph isomorphism is low for PP
- Group-theoretic algorithms and graph isomorphism
Cited in
(9)- Solvable black-box group problems are low for \(\mathrm{PP}\)
- The hidden subgroup problem and MKTP
- Quantum algorithms for a set of group theoretic problems
- scientific article; zbMATH DE number 1104166 (Why is no real title available?)
- LWPP and WPP are not uniformly gap-definable
- Counting Complexity of Solvable Black-Box Group Problems
- SZK proofs for black-box group problems
- The Complexity of Black-Box Ring Problems
- Graph Isomorphism is in SPP
This page was built for publication: Solvable black-box group problems are low for PP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1390854)
