On the complexity of some problems on groups input as multiplication tables
From MaRDI portal
Publication:5956010
DOI10.1006/jcss.2001.1764zbMath0988.68080OpenAlexW2039116808MaRDI QIDQ5956010
Pierre McKenzie, Peter Kadau, David Mix Barrington, Klaus-Joern Lange
Publication date: 22 July 2002
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.2001.1764
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (8)
Uniform constant-depth threshold circuits for division and iterated multiplication. ⋮ Synchronizing words and monoid factorization, yielding a new parameterized complexity class? ⋮ Linear time algorithms for Abelian group isomorphism and related problems ⋮ The Bounded and Precise Word Problems for Presentations of Groups ⋮ On theories of bounded arithmetic for \(\mathrm{NC}^1\) ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Generation problems
Cites Work
- Parallel algorithms for solvable permutation groups
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Oracle branching programs and Logspace versus \(P^*\)
- Complete problems for deterministic polynomial time
- Improved depth lower bounds for small distance connectivity
- On uniformity within \(NC^ 1\)
- Division in logspace-uniformNC1
- Parity, circuits, and the polynomial-time hierarchy
- Constant Depth Reducibility
- A taxonomy of problems with fast parallel algorithms
- Log Depth Circuits for Division and Related Problems
- Problems complete for deterministic logarithmic space
- New problems complete for nondeterministic log space
- On Relating Time and Space to Size and Depth
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: On the complexity of some problems on groups input as multiplication tables
