On the Minimal Polynomial

Thanh Minh Hoang and Thomas Thierauf

Abstract:
We compare the constant term of the minimal polynomial with the constant term of the characteristic polynomial. The latter is known to be computable in the logspace counting class GapL. We show that this holds also for the minimal polynomial if and only if the logspace exact counting class C=L is closed under complement. The latter condition is one of the main open problems in this area.

As an application of our techniques we show that the problem to decide whether a matrix is diagonalizable is complete for AC0(C=L), the AC0-closure of C=L.