Mortality for 2 ×2 Matrices Is NP-Hard
From MaRDI portal
Publication:2912716
DOI10.1007/978-3-642-32589-2_16zbMath1365.68265OpenAlexW1488228805MaRDI QIDQ2912716
Paul C. Bell, Igor Potapov, Mika Hirvensalo
Publication date: 25 September 2012
Published in: Mathematical Foundations of Computer Science 2012 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-32589-2_16
Related Items (11)
The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete ⋮ Matrix Semigroup Freeness Problems in SL $$(2,\mathbb {Z})$$ ⋮ Vector Ambiguity and Freeness Problems in SL $$(2,\mathbb {Z})$$ ⋮ Vector and scalar reachability problems in \(\operatorname{SL}(2, \mathbb{Z})\) ⋮ Unnamed Item ⋮ On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond ⋮ On finite monoids over nonnegative integer matrices and short killing words ⋮ On Affine Reachability Problems ⋮ On the Mortality Problem: From Multiplicative Matrix Equations to Linear Recurrence Sequences and Beyond ⋮ On Nonnegative Integer Matrices and Short Killing Words ⋮ On eventual non-negativity and positivity for the weighted sum of powers of matrices
This page was built for publication: Mortality for 2 ×2 Matrices Is NP-Hard