O permanente de uma matriz A de tamanho n times n é definido por:
Per(A)=sumsigma in Sn A1 sigma(1) A2 sigma(2) cdots An sigma(n)
Vimos no exercício 9.7 que é possível calcular o determinante de uma matriz n times n em tempo polinomial em n (ou seja, existem constantes c e d tais que o número de multiplicações é limitado superiormente pelo polinômio c n^d ). O problema é: Mostrar que existem ced tais que para cada n, o permanente n times n pode ser calculado em no máximo cn ^d 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 AinR^ntimes n por
Per(A)=sumsigmain SnA1sigma(1)A2sigma(2)cdots Ansigma(n)
e pergunta se existe um algoritmo que o compute em no máximo c,n^d operações de soma e multiplicação. Para abordar isso, vamos recorrer à teoria de complexidade de contagem, em particular à classe #P e ao fato de que o permanente é #P-completo.

Passo 2

Definimos a classe #P como o conjunto de problemas de contagem de soluções de problemas de decisão em NP. Um problema em #P é #P-completo se todo outro problema de #P 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 FP (funções computáveis em tempo polinomial) que resolve qualquer problema de #P, ou seja, #P=FP.

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.

Exercícios de Livros Relacionados