Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR01-028 | 16th March 2001 00:00

The Complexity of the Minimal Polynomial

RSS-Feed




TR01-028
Authors: Thanh Minh Hoang, Thomas Thierauf
Publication: 23rd April 2001 11:08
Downloads: 1763
Keywords: 


Abstract:

We investigate the computational complexity
of the minimal polynomial of an integer matrix.

We show that the computation of the minimal polynomial
is in AC^0(GapL), the AC^0-closure of the logspace
counting class GapL, which is contained in NC^2.
Our main result is that the problem is hard for GapL
(under AC^0 many-one reductions).
The result extends to the verification of
all invariant factors of an integer matrix.

Furthermore, we consider the complexity of the problem
whether an integer matrix is diagonalizable.
We show that this problem lies in AC^0(GapL) and
is hard for AC^0(CL) (under AC^0 many-one reductions).



ISSN 1433-8092 | Imprint