Solvable black-box group problems are low for PP
type: Item
instance of: scholarly article
title: Solvable black-box group problems are low for PP
zbMATH Open document ID: 0901.68072
DOI: 10.1016/S0304-3975(96)00100-4
author: Vikraman Arvind
author: N. V. Vinodchandran
published in: Theoretical Computer Science
publication date: 1998-07-22T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 1177587
zbMATH Keywords: oracle algorithm
MaRDI profile type: Publication
cites work: Bounded Round Interactive Proofs in Finite Groups
cites work: Fast Monte Carlo algorithms for permutation groups
cites work: Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
cites work: Does co-NP have short interactive proofs ?
cites work: Q5848209
cites work: Q4273602
cites work: Q3253828
cites work: Group-theoretic algorithms and graph isomorphism
cites work: Graph isomorphism is low for PP
cites work: Q4230332
cites work: Graph isomorphism is in the low hierarchy
Recommended article: Solvable black-box group problems are low for PP
Recommended article: Q4370033
Recommended article: Counting Complexity of Solvable Black-Box Group Problems
Recommended article: Sufficient Conditions for Intractability over Black-Box Groups: Generic Lower Bounds for Generalized DL and DH Problems
Recommended article: SZK proofs for black-box group problems
Recommended article: SZK Proofs for Black-Box Group Problems
Recommended article: Q4240509
Recommended article: Solvable Group Isomorphism Is (Almost) in NP ∩ coNP
Recommended article: Quite free complicated abelian groups, pcf and black boxes
Recommended article: Breaking the nlog n Barrier for Solvable-Group Isomorphism
description: scientific article; zbMATH DE number 1177587