Algoritmos surpreendentes para contar problemas

54

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:

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?

Ashley Montanaro
fonte
8
BTW, muitos outros problemas de contagem se reduzem à computação do determinante. O determinante inteiro está completo para a classe GapL, que contém #L.
5501

Respostas:

11

Não sei se os seguintes problemas reduzem ou não o cálculo do determinante, mas listarei de qualquer maneira:

v0vfvfv0

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 .

f:{0,1}n{0,1}xf(x)=1Uf|x|0|x|f(x)|1UfHn|0|0

Mateus de Oliveira Oliveira
fonte
Obrigado - os itens (2) e (3) são interessantes, mas de alguma forma não são exatamente o que eu estava procurando; problemas de contagem com largura de árvore delimitada parecem mais casos especiais em que a estrutura com a qual você está trabalhando é delimitada polinomialmente. Eu estava mais interessado nos casos em que existem "realmente" exponencialmente muitos objetos a serem contados, mas eles podem, de alguma forma, ser contados magicamente em tempo polinomial.
Ashley Montanaro #
Isso não significa que, se você usar uma codificação unária, o algoritmo precisará de tempo exponencial apenas para escrever o número? É possível que esse problema seja superado usando a codificação binária, mas isso me parece contraditório.
Antonio Valerio Miceli-Barone
2
@ Miceli-Barone, o que você diz se aplica a praticamente qualquer algoritmo de tempo poli que gera um número. O determinante em si seria bastante grande no pior dos casos, em unário.
Rafael
(n+1)n+122n
11

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.

Tyson Williams
fonte