Existem alguns problemas de contagem que envolvem contar exponencialmente muitas coisas (em relação ao tamanho da entrada) e ainda possuem algoritmos determinísticos surpreendentes em tempo polinomial exato. Exemplos incluem:
- Contando combinações perfeitas em um gráfico planar (o algoritmo FKT ), que é a base para o funcionamento dos algoritmos holográficos .
- Contando árvores de abrangência em um gráfico (através do teorema da árvore matricial de Kirchhoff ).
Um passo fundamental nesses dois exemplos é reduzir o problema de contagem para calcular o determinante de uma determinada matriz. Um determinante é ele próprio, é claro, uma soma de muitas coisas exponencialmente, mas pode surpreendentemente ser computado em tempo polinomial.
Minha pergunta é: existe algum algoritmo exato e determinístico "surpreendentemente eficiente" conhecido por contar problemas que não se reduz à computação de um determinante?
cc.complexity-theory
counting-complexity
big-picture
Ashley Montanaro
fonte
fonte
Respostas:
Não sei se os seguintes problemas reduzem ou não o cálculo do determinante, mas listarei de qualquer maneira:
2) Contando o número de soluções de problemas definíveis na lógica MSO em estruturas de largura de árvore limitada. Veja, por exemplo, o artigo que se baseia em obras de Courcelle, Arnborg e outros .
fonte
Contar o número de pontos de rede em um polítopo racional (quando a dimensão é constante) em tempo polinomial , devido a Alexander Barvinok.
fonte
Na estrutura de Holant, existem vários casos que são razões tratáveis (por não triviais) que não sejam através de portas de correspondência em gráficos planares.
1) Portões de Fibonacci
2) Qualquer conjunto de assinaturas afins .
3) #CSPs ponderados não negativos
...para nomear alguns.
Além disso, o teorema BEST fornece um algoritmo de tempo polinomial para contar o número de circuitos eulerianos em um gráfico direcionado, embora parte do algoritmo use um cálculo determinante.
fonte