Pesquisa sobre #P e / ou problemas de contagem

23

Alguém pode sugerir uma pesquisa boa e recente sobre a contagem de problemas e / ou problemas que são #P.

cc.complexity-theory reference-request counting-complexity Tayfun Pay
fonte
Esses documentos parecem poucos e distantes entre si. Eu estaria muito interessado em um bom trabalho de pesquisa sobre o assunto. Observei que a Wikipedia nem sequer contém uma "Lista de problemas com # P-complete". Também é interessante que houvesse três perguntas hoje solicitando referências para problemas de contagem.
bbejot

Respostas:

13

L. Fortnow. Contando complexidade . Em L. Hemaspaandra e A. Selman, editores, Complexity Theory Retrospective II, páginas 81-107. Springer, 1997

Isso fornece mais pontos de vista da complexidade estrutural (classes de complexidade, oráculos etc.) e discute outras classes relacionadas ao #P. Embora seja de quase 15 anos atrás, na verdade não é tão desatualizado em termos de resultados.

Joshua Grochow
fonte
1
@ Tayfun: O que está faltando? Não que eu necessariamente discorde de você, estou apenas curioso sobre o que especificamente você gostaria de ter visto além.
Joshua Grochow
12

Experimente as notas de aula ETH de Mark Jerrum . Uma versão gratuita está disponível em seu site aqui .

RJK
fonte
Eu acho que encontrei de graça! ;)
Tayfun Pay
9

Pinyan Lu publicou uma pesquisa via ECCC em meados de 2011. Compara três estruturas de contagem populares:

  • Contando Homomorfismos de Gráficos,
  • Satisfação de restrição de contagem (#CSP) e
  • a estrutura de Holant
  • (e restrições dessas estruturas).

Ele também discute os teoremas atuais da dicotomia e as técnicas de prova usadas para obtê-los.

Xi Chen publicou uma pesquisa como coluna convidada para o SIGACT News no final de 2011. Ele discute os resultados e as técnicas que levaram e incluem seus trabalhos com Jin-Yi Cai e Pinyan Lu sobre dicotomias para contar homomorfismos de gráfico definidos por um gráfico de destino não direcionado com pesos complexos ( arXiv ) e #CSPs com ponderação não-negativa ( arXiv ).

Na mesma época, Cai e Chen publicaram uma dicotomia para #CSPs de peso complexo ( arXiv ), que Cai discutiu em um post convidado no blog Godel's Lost Letter e P = NP .

Tyson Williams
fonte
Agradável! Eu vou ler isso!
Tayfun Pay
3

Outra estrutura de problemas de contagem vem da computação do polinômio Tutte de um gráfico. Nesta estrutura, quaisquer dois números complexos definem um problema de contagem.

O livro Matroid Applications dedica o capítulo 6 ao The Tutte Polynomial and Its Applications . O link anterior é uma varredura desse capítulo no site de James Oxley , um dos co-autores. No semestre passado, ele deu um curso baseado nesse capítulo.

Outra boa referência sobre esse tópico é este artigo semelhante a uma pesquisa de Gales.

Tyson Williams
fonte