Complexity classes of equivalence problems revisited
DOI10.1016/j.ic.2011.01.006zbMath1238.68061OpenAlexW2160461541MaRDI QIDQ716333
Joshua A. Grochow, Lance J. Fortnow
Publication date: 28 April 2011
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2011.01.006
computational complexitynormal formquantum computationisomorphism problemoracleequivalence relationprobabilistic computation
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (6)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The shrinking property for NP and coNP
- Quantum mechanical algorithms for the nonabelian hidden subgroup problem
- Turing machines that take advice
- Statistical zero-knowledge languages can be recognized in two rounds
- \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
- BPP and the polynomial hierarchy
- On self-reducibility and weak P-selectivity
- NP is as easy as detecting unique solutions
- Does co-NP have short interactive proofs ?
- Probabilistic quantifiers and games
- Probabilistic algorithm for testing primality
- Efficient representation of perm groups
- A very hard log-space counting class
- Symmetric alternation captures BPP
- A taxonomy of complexity classes of functions
- Perceptrons, PP, and the polynomial hierarchy
- More on BPP and the polynomial-time hierarchy
- An oracle builder's toolkit
- The counting complexity of group-definable languages
- The computational complexity of equivalence and isomorphism problems
- PRIMES is in P
- Competing provers yield improved Karp-Lipton collapse results
- Two queries
- A V log V algorithm for isomorphism of triconnected planar graphs
- A model of set-theory in which every set of reals is Lebesgue measurable
- Hypergraph isomorphism and structural equivalence of Boolean functions
- Pseudorandom walks on regular digraphs and the RL vs. L problem
- On the algorithmic insolvability of the word problem in group theory
- Equivalence Relations, Invariants, and Normal Forms
- Positive Relativizations of Complexity Classes
- Quantum lower bound for the collision problem
- Hidden translation and orbit coset in quantum computing
- Exponential algorithmic speedup by a quantum walk
- Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
- A survey of one-way functions in complexity theory
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- A Fast Monte-Carlo Test for Primality
- Word Problems Solvable in Logspace
- New Collapse Consequences of NP Having Small Circuits
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- On the Power of Quantum Computation
- The Formula Isomorphism Problem
- Quantum Computation and Lattice Problems
- Computing Solutions Uniquely Collapses the Polynomial Hierarchy
- Computational Complexity
- The Complexity of Computing the Size of an Interval
- EFFICIENT QUANTUM ALGORITHMS FOR SOME INSTANCES OF THE NON-ABELIAN HIDDEN SUBGROUP PROBLEM
- A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
This page was built for publication: Complexity classes of equivalence problems revisited
