ECCC-Report TR01-028https://eccc.weizmann.ac.il/report/2001/028Comments and Revisions published for TR01-028en-usMon, 23 Apr 2001 11:08:27 +0300
Paper TR01-028
| The Complexity of the Minimal Polynomial |
Thanh Minh Hoang,
Thomas Thierauf
https://eccc.weizmann.ac.il/report/2001/028We 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).
Mon, 23 Apr 2001 11:08:27 +0300https://eccc.weizmann.ac.il/report/2001/028