Strong NP-completeness of a matrix similarity problem

DOI10.1016/0304-3975(96)00103-XMaRDI QIDQ671534zbMATHOpenAlexFDO

Authors Valentin E. Brimkov, Bruno Codenotti, Mauro Leoncini, Giovanni Resta

Publication date 27 February 1997

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(96)00103-x

zbMATH Keywords

computational complexitycondition numbersimilarity transformation

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Finding well-conditioned similarities to block-diagonalize nonsymmetric matrices is NP-hard
• scientific article; zbMATH DE number 741115
• The P-matrix problem is co-NP-complete

Cites work

• scientific article; zbMATH DE number 4213315 (Why is no real title available?)
• scientific article; zbMATH DE number 52121 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3239038 (Why is no real title available?)
• An Algorithm for Computing Reducing Subspaces by Block Diagonalization
• Checking robust nonsingularity is NP-hard
• Computing Exact Componentwise Bounds on Solutions of Lineary Systems with Interval Data is NP-Hard
• Finding well-conditioned similarities to block-diagonalize nonsymmetric matrices is NP-hard
• Ill-Conditioned Eigensystems and the Computation of the Jordan Canonical Form
• Strong NP-completeness of a matrix similarity problem
• The Condition Number of Equivalence Transformations That Block Diagonalize Matrix Pencils

Cited in

(4)

• Strong NP-completeness of a matrix similarity problem
• Band-restricted diagonally dominant matrices: computational complexity and application
• An \(NC^ 2\) algorithm for testing similarity of matrices
• scientific article; zbMATH DE number 741115 (Why is no real title available?)

This page was built for publication: Strong NP-completeness of a matrix similarity problem

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