Se sabe que se puede calcular exactamente el determinante de una matriz en el espacio determinístico log 2 ( n ) . ¿Cuáles serían las implicaciones de complejidad de aproximar el determinante de una matriz real, de la norma como máximo 1 ( ‖ A ‖ ≤ 1 ) en el espacio logarítmico aleatorizado, por decir, una precisión 1 / poli ?
A este respecto, ¿cuál sería la aproximación "correcta" que pedir: multiplicativa o aditiva? (Ver una de las respuestas a continuación).
determinant
cc.complexity-theory
Lior Eldar
fuente
fuente
Respuestas:
Con el riesgo de no haber entendido correctamente los detalles de la pregunta: ser capaz de aproximar el determinante dentro de cualquier factor requiere poder decidir si una matriz cuadrada es singular o no, lo que debería tener algunas consecuencias.
Por un lado, ofrece una prueba aleatoria de si un gráfico general tiene una coincidencia perfecta (a través de la matriz de Tutte y Schwarz-Zippel). No creo que este último se conozca en el espacio de registro aleatorio (por ejemplo, Complexity Zoo enumera la coincidencia perfecta bipartita como difícil para NL).
fuente