O permanente de uma matriz de tamanho é definido por:
Vimos no exercício 9.7 que é possível calcular o determinante de uma matriz em tempo polinomial em (ou seja, existem constantes e tais que o número de multiplicações é limitado superiormente pelo polinômio ). O problema é: Mostrar que existem ced tais que para cada , o permanente pode ser calculado em no máximo cn operações de soma e multiplicação (vale também utilizar constantes, mas não valem comparações), ou mostrar que tais c ed não podem existir.
Passo 1
O enunciado define o permanente de uma matriz por
e pergunta se existe um algoritmo que o compute em no máximo operações de soma e multiplicação. Para abordar isso, vamos recorrer à teoria de complexidade de contagem, em particular à classe e ao fato de que o permanente é -completo.
Passo 2
Definimos a classe como o conjunto de problemas de contagem de soluções de problemas de decisão em . Um problema em é -completo se todo outro problema de pode ser reduzido a ele em tempo polinomial (por reduções de Turing polinomiais). Se conseguíssemos computar o permanente em tempo polinomial, teríamos um procedimento em (funções computáveis em tempo polinomial) que resolve qualquer problema de , ou seja, .
Passo 3
Mostramos que contar emparelhamentos perfeitos em um grafo bipartido reduz-se diretamente ao cálculo de permanente. Seja
Então cada permutação corresponde a um emparelhamento perfeito de . Logo
Passo 4
Em 1979, Leslie Valiant provou que o problema de contar emparelhamentos perfeitos em grafos bipartidos é #P-completo. Pela redução acima, segue que calcular o permanente de uma matriz geral de zeros e uns também é #P-completo. Consequentemente, o permanente de uma matriz arbitrária é #P-completo.
Passo 5
Se existisse um algoritmo que computasse Per(A) em no máximo c,n^d operações de soma e multiplicação, então teríamos Perin FP, implicando #P=FP. Isso, por sua vez, levaria a P=NP e ao colapso de hierarquias clássicas da teoria da complexidade, o que é amplamente considerado improvável.
Resposta
Não existem constantes c e d tais que se possa calcular Per(A) para todas as matrizes ntimes n em no máximo c,n^d operações de soma e multiplicação, a menos de se admitir que #P=FP (e portanto P=NP), hipótese considerada inverossímil.
Álgebra Linear e Geometria Analítica - Gregorio Malajovich - Álgebra Linear - 4ª Edição - Capítulo 9.Exercícios - Ex. Problema em aberto № 2