The Orbit Problem Is in the GapL Hierarchy

DOI10.1007/978-3-540-69733-6_17MaRDI QIDQ3511324zbMATH OpenOpenAlexFDO

Authors Vikraman 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)

Recommendations

• The orbit problem is in the GapL hierarchy
• scientific article; zbMATH DE number 7559115
• Left-eigenvectors are certificates of the Orbit problem
• On the complexity of the orbit problem
• The orbit problem in higher dimensions

Cites work

• scientific article; zbMATH DE number 176871 (Why is no real title available?)
• Polynomial-time algorithm for the orbit problem
• Relationships among $PL$, $\#L$, and the determinant
• The complexity of matrix rank and feasible systems of linear equations
• The complexity of the characteristic and the minimal polynomial.
• Uniform constant-depth threshold circuits for division and iterated multiplication.

Cited in

(3)

• Hypergeometric dispersion and the orbit problem
• Continuous-time orbit problems are decidable in polynomial-time
• The orbit problem is in the GapL hierarchy

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3511324)