En realidad, supongo que la respuesta es técnicamente "sí", ya que el cómputo de la permanente es #P-completo, pero eso no es muy satisfactorio. Así que aquí está lo que me refiero:
Kirchhoff del teorema dice que si el Laplaciano de la matriz de un grafo, y cortar una fila y una columna, entonces el determinante de la matriz resultante es igual al número de árboles de expansión de la gráfica. Sería bueno tener algo de análogo de este por otros puntos de la polinomio de Tutte, pero esto es en general mucho pedir: el determinante puede ser calculado en el polinomio de tiempo, pero los problemas tales como el conteo de 3 colorantes son #P-duro.
Sin embargo, si utilizamos el permanente cambio de los determinantes, que no se ejecuten en estas complejidad de la teoría de los problemas, al menos. Así, dado un grafo G de n vértices, podemos construir una matriz de tamaño alrededor de nxn cuyos permanente es el número de 3-coloraciones de G?
(El secreto de la motivación subyacente aquí es una vaga esperanza personal que podemos extender la analogía entre el Laplaciano de la matriz y el operador Laplaciano [no, la nomenclatura no es una coincidencia total] a las analogías entre otras matrices y general elíptica operadores y, a continuación, probar algún tipo de índice de "teorema", que podría incluso más en forma especulativa, aquí] nos ayuda a entender por qué la gráfica de isomorfismo es duro, probar o construir un contraejemplo para la reconstrucción de la conjetura, de demostrar la hipótesis de Riemann, y alcanzar la paz mundial, para siempre).
