The Orbit Problem Is in the GapL Hierarchy

DOI10.1007/978-3-540-69733-6_17zbMath1148.68384OpenAlexW1829759619MaRDI QIDQ3511324

V. Arvind, T. C. Vijayaraghavan

Publication date: 10 July 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-69733-6_17

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (2)

The orbit problem is in the GapL hierarchy ⋮ Continuous-time orbit problems are decidable in polynomial-time

Cites Work

• The complexity of the characteristic and the minimal polynomial.
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• The complexity of matrix rank and feasible systems of linear equations
• Polynomial-time algorithm for the orbit problem
• Relationships among $PL$, $\#L$, and the determinant
• Unnamed Item

This page was built for publication: The Orbit Problem Is in the GapL Hierarchy