Solvable black-box group problems are low for PP

DOI10.1016/S0304-3975(96)00100-4zbMath0901.68072MaRDI QIDQ1390854

V. Arvind, N. V. Vinodchandran

Publication date: 22 July 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

oracle algorithm

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (5)

Quantum property testing of group solvability ⋮ LWPP and WPP are not uniformly gap-definable ⋮ Graph Isomorphism is in SPP ⋮ The hidden subgroup problem and MKTP ⋮ Quantum Algorithms for a Set of Group Theoretic Problems

Cites Work

• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Does co-NP have short interactive proofs ?
• Graph isomorphism is in the low hierarchy
• Group-theoretic algorithms and graph isomorphism
• Graph isomorphism is low for PP
• Fast Monte Carlo algorithms for permutation groups
• Bounded Round Interactive Proofs in Finite Groups
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Solvable black-box group problems are low for PP