The counting complexity of group-definable languages
From MaRDI portal
Publication:1575546
DOI10.1016/S0304-3975(98)00218-7zbMath0944.68067MaRDI QIDQ1575546
V. Arvind, N. V. Vinodchandran
Publication date: 21 August 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (2)
Polynomial-time axioms of choice and polynomial-time cardinality ⋮ Complexity classes of equivalence problems revisited
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- Self-witnessing polynomial-time complexity and prime factorization
- Graph isomorphism is low for PP
- A note on the graph isomorphism counting problem
- Gap-definable counting classes
- PP is as Hard as the Polynomial-Time Hierarchy
- Bounded Round Interactive Proofs in Finite Groups
This page was built for publication: The counting complexity of group-definable languages
