El algoritmo más rápido conocido para calcular las ejecuciones permanentes en tiempo exponencial [matemática] O (2 ^ nn) [/ matemática]. Dado que el problema es # P-completo, incluso para {0, 1} matrices (LG Valiant, “La complejidad de calcular el permanente”, 1979), la existencia de un algoritmo de tiempo polinomial implicaría P = NP = #P, lo cual se cree que es muy improbable.
Dado que el permanente tiene la mayor longitud de polinomio, si hay un algoritmo de tiempo polinómico para decidir si el permanente es al menos [math] k [/ math], entonces podríamos usarlo para realizar una búsqueda binaria para calcular el valor exacto del permanente en tiempo polinómico, por lo que también es muy poco probable. Sin embargo, existe un esquema de aproximación aleatoria totalmente polinomial (M. Jerrum, E. Vigoda, “Un algoritmo de aproximación de tiempo polinomial para el permanente de una matriz con entradas no negativas”, 2000), que podría ser útil si el permanente no está muy cerca de [matemáticas] k [/ matemáticas].
El artículo de Valiant también muestra cómo calcular el módulo permanente [matemática] 2 ^ i [/ matemática] en el tiempo [matemática] O (n ^ {4i-3}) [/ matemática], para que podamos encontrar la más pequeña [matemática] 2 ^ i [/ math] dividiendo el permanente en el tiempo [math] O (n ^ {4i-3}) [/ math], que es polinomial cuando se sabe que [math] i [/ math] es una pequeña constante.
- Álgebra lineal: ¿Cómo definimos el determinante de un endomorfismo de forma independiente de la base?
- ¿Cuál es una explicación técnica laica de la descomposición armónica de Pisarenko, su utilidad y su diferencia con una transformada de Fourier?
- ¿Son los números y vectores complejos sobre [math] \ mathbb {R} ^ {2} [/ math] (2-tuple) la misma cosa?
- ¿Cómo se escriben las ecuaciones de movimientos de partículas acopladas utilizando valores propios?
- ¿Cuál es el significado de la descomposición propia?